Показано, що поліноміального відносно М в середньому алгоритму для визначення оптимального розв'язку задачі про покриття множинами, яка відрізняється від вихіднох в одній позиції матриці обмежень, не існує, якщо відштовхуватися від оптимального розв'язку вихідної задачі.
