Складність апроксимації
В інформатиці складність апроксимації — це галузь вивчення обчислювальної складності пошуку розв'язків задач оптимізації, близьких до оптимальних.
Галузь вивчення[ред. | ред. код]
Складність апроксимації доповнює вивчення апроксимаційних алгоритмів доведенням для деяких задач обмежень на параметри, за якими розв'язки задач можна ефективно апроксимувати. Як правило, такі обмеження показують причини, через які задача стає NP-складною, в припущенні, що апроксимація з поліноміальним часом розв'язування задачі неможлива, якщо тільки не NP=P. Деякі результати за складністю апроксимації, однак, спираються на інші гіпотези, з яких особливо примітна гіпотеза про ігри з єдиною відповіддю[en][1][2][3].
Історія[ред. | ред. код]
Від початку 1970-х відомо, що багато задач оптимізації не можна розв'язати за поліноміальний час, якщо тільки не NP=P, але в багатьох таких задачах оптимальний розв'язок можна до деякої міри ефективно апроксимувати. На початку 1990-х, у міру розвитку теорії ймовірнісно перевірних доведень[en], стало ясно, що існують обмеження на ступінь апроксимації багатьох задач оптимізації — для багатьох задач існує поріг, за яким апроксимація стає NP-складною. Теорія складності апроксимації вивчає такі пороги апроксимації.
Приклади[ред. | ред. код]
Прикладом NP-складної задачі оптимізації, яку важко апроксимувати, є задача про покриття множини[4].
Див. також[ред. | ред. код]
Примітки[ред. | ред. код]
- ↑ Johan Håstad. Some Optimal Inapproximability Results // Journal of the ACM. — 1999. — 21 квітня.
- ↑ Subhash Khot. Proceedings of the thirty-fourth annual ACM symposium on Theory of computing. — 2002. — С. 767–775. — ISBN 1-58113-495-9. — DOI:
- ↑ Erica Klarreich. Approximately Hard: The Unique Games Conjecture. — 2011. — 6 жовтня.
- ↑ Subhash Khot, Oded Regev. Vertex cover might be hard to approximate to within 2-ε // IEEE Conference on Computational Complexity. — 2003. — 21 квітня. — С. 379–.
Література[ред. | ред. код]
Посилання[ред. | ред. код]
- CSE 533: Теорема PCP і складність апроксимації, восени 2005, короткий виклад Гурусвамі і О'Доннелла з Університету Вашингтону