Твердость приближения - Hardness of approximation

В Информатика, твердость приближения это область, изучающая алгоритмическая сложность поиска почти оптимальных решений проблемы оптимизации.

Объем

Трудность аппроксимации дополняет изучение аппроксимационные алгоритмы путем доказательства для определенных задач предела факторов, с помощью которых можно эффективно аппроксимировать их решение. Обычно такие пределы показывают коэффициент приближения, за пределами которого проблема становится NP-жесткий, подразумевая, что нахождение полиномиальное время приближение для задачи невозможно, если NP = P. Однако некоторая жесткость результатов аппроксимации основана на других гипотезах, среди которых следует отметить догадка уникальных игр.

История

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

Трудность теории приближений связана с изучением порога приближения таких задач.