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