В информатике сложность аппроксимации — это область, изучающая алгоритмическую сложность поиска почти оптимальных решений задач оптимизации .
Трудность аппроксимации дополняет изучение алгоритмов аппроксимации , доказывая для некоторых задач предел на факторы, с помощью которых их решение может быть эффективно аппроксимировано. Обычно такие пределы показывают фактор аппроксимации, за пределами которого задача становится NP-трудной , подразумевая, что нахождение полиномиальной аппроксимации для задачи невозможно, если только NP=P . Некоторые результаты по трудности аппроксимации, однако, основаны на других гипотезах, среди которых примечательной является гипотеза уникальных игр .
С начала 1970-х годов было известно, что многие задачи оптимизации не могут быть решены за полиномиальное время, если только P = NP , но во многих из этих задач оптимальное решение может быть эффективно приближено до определенной степени. В 1970-х годах Теофило Ф. Гонсалес и Сартадж Сахни начали изучение сложности аппроксимации, показав, что некоторые задачи оптимизации являются NP-трудными даже для приближения с заданным отношением аппроксимации . То есть для этих задач существует порог, такой что любое приближение за полиномиальное время с отношением аппроксимации за пределами этого порога может быть использовано для решения NP-полных задач за полиномиальное время. [1] В начале 1990-х годов, с развитием теории PCP , стало ясно, что многие другие задачи аппроксимации трудно приблизить, и что (если только P = NP) многие известные алгоритмы аппроксимации достигают наилучшего возможного отношения аппроксимации.
Теория сложности аппроксимации занимается изучением порога аппроксимации таких задач.
Пример NP-трудной задачи оптимизации, которую трудно аппроксимировать, см. в set cover .