Анотація. Показано, що для NP -повних задач трудомістким є навіть обчислення кулі стійкості радіуса 1 оптимального розв’язку (тобто при P ≠ NP для цього розв’язку не існує поліноміального алгоритму). При використанні жадібних алгоритмів для задачі про покриття множинами (задачі про рюкзак) при радіусі стійкості r = O (1) існують поліноміальні алгоритми обчислення кулі стійкості радіуса r lnm -наближеного розв’язку (1-наближеного розв’язку).

Ключові слова: складність анализу стійкості, радіус стійкості задачі, куля стійкості радіуса r ε -наближеного розв’язку задачі.