В информатике , твердость приближения является полем, изучающая алгоритмическая сложность нахождения вблизи оптимального решения задач оптимизации .
Сфера [ править ]
Трудность аппроксимации дополняет изучение алгоритмов аппроксимации , доказывая для некоторых задач ограничение на факторы, с помощью которых их решение может быть эффективно аппроксимировано. Обычно такие ограничения показывают коэффициент приближения , после которого проблема становится NP-трудной , подразумевая , что нахождение полиномиальное время приближения для задачи невозможно , если NP = P . Однако некоторая сложность результатов аппроксимации основана на других гипотезах, среди которых стоит выделить гипотезу об уникальных играх .
История [ править ]
С начала 1970-х годов было известно, что многие задачи оптимизации не могут быть решены за полиномиальное время, если P = NP , но во многих из этих задач оптимальное решение может быть эффективно аппроксимировано до определенной степени. В 1970-х годах Теофило Ф. Гонсалес и Сартадж Сахни начали изучение точности аппроксимации, показав, что некоторые задачи оптимизации NP-трудны даже для аппроксимации с точностью до заданного отношения аппроксимации . То есть для этих задач существует порог, такой, что любое приближение за полиномиальное время с коэффициентом аппроксимации, превышающим этот порог, может быть использовано для решения NP-полных задач за полиномиальное время. [1] В начале 1990-х, с развитием PCP Теории стало ясно, что многие другие задачи аппроксимации трудно аппроксимировать, и что (если P = NP) многие известные алгоритмы аппроксимации достигают наилучшего возможного отношения приближения.
Трудность теории приближений связана с изучением порога приближения таких задач.
Примеры [ править ]
Для примера NP-сложной задачи оптимизации, которую трудно аппроксимировать, см. Обложку набора .
См. Также [ править ]
Ссылки [ править ]
- ^ Сахни, Сартадж ; Гонсалес, Теофили (1976), " Р проблемы -полной аппроксимации", Журнал ACM , 23 (3): 555-565, DOI : 10,1145 / 321958,321975 , ЛВП : 10338.dmlcz / 103883 , МР 0408313.
Дальнейшее чтение [ править ]
- Тревизан, Лука (27 июля 2004 г.), Непроксимируемость задач комбинаторной оптимизации (PDF)
Внешние ссылки [ править ]
- CSE 533: Теорема PCP и твердость аппроксимации, осень 2005 г. , программа Вашингтонского университета , Венкатесан Гурусвами и Райан О'Доннелл
