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

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