Сложность аппроксимации

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

Область изучения

Сложность аппроксимации дополняет изучение аппроксимационных алгоритмов путём доказательства для некоторых задач ограничений на параметры, по которым решения задач можно эффективно аппроксимировать. Как правило, такие ограничения показывают причины, по которым задача становится NP-трудной, в предположении, что аппроксимация с полиномиальным временем решения задачи невозможна, если только не NP=P. Некоторые результаты по трудности аппроксимации, однако, опираются на другие гипотезы, из которых особенно примечательна гипотеза об играх с единственным ответом[1] [2][3].

История

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

Примеры

Примером NP-сложной задачи оптимизации, которую трудно аппроксимировать, служит задача о покрытии множества[4].

См. также

  • Теорема PCP
  • Гипотеза об играх с единственным ответом

Примечания

  1. Johan Håstad. Some Optimal Inapproximability Results // Journal of the ACM. — 1999.
  2. Subhash Khot. Proceedings of the thirty-fourth annual ACM symposium on Theory of computing. — 2002. — С. 767–775. — ISBN 1-58113-495-9. doi:10.1145/509907.510017.
  3. Erica Klarreich. Approximately Hard: The Unique Games Conjecture. — 2011-10-06.
  4. Subhash Khot, Oded Regev. Vertex cover might be hard to approximate to within 2-ε // IEEE Conference on Computational Complexity. — 2003. С. 379–.

Дальнейшее чтение

Ссылки

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.