Складність апроксимації

В інформатиці складність апроксимації — це галузь вивчення обчислювальної складності пошуку розв'язків задач оптимізації, близьких до оптимальних.

Галузь вивчення

Складність апроксимації доповнює вивчення апроксимаційних алгоритмів доведенням для деяких задач обмежень на параметри, за якими розв'язки задач можна ефективно апроксимувати. Як правило, такі обмеження показують причини, через які задача стає NP-складною, в припущенні, що апроксимація з поліноміальним часом розв'язування задачі неможлива, якщо тільки не NP=P. Деякі результати за складністю апроксимації, однак, спираються на інші гіпотези, з яких особливо примітна гіпотеза про ігри з єдиною відповіддю[1][2][3].

Історія

Від початку 1970-х відомо, що багато задач оптимізації не можна розв'язати за поліноміальний час, якщо тільки не NP=P, але в багатьох таких задачах оптимальний розв'язок можна до деякої міри ефективно апроксимувати. На початку 1990-х, у міру розвитку теорії ймовірнісно перевірних доведень, стало ясно, що існують обмеження на ступінь апроксимації багатьох задач оптимізації — для багатьох задач існує поріг, за яким апроксимація стає NP-складною. Теорія складності апроксимації вивчає такі пороги апроксимації.

Приклади

Прикладом NP-складної задачі оптимізації, яку важко апроксимувати, є задача про покриття множини[4].

Див. також

PCP-теорема
Гіпотеза про ігри з єдиною відповіддю

Примітки

Johan Håstad. Some Optimal Inapproximability Results // Journal of the ACM. — 1999. — 3 листопада.
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.
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. — 3 листопада. — С. 379–.

Література

Огляд для швидкого занурення в тему

Посилання

CSE 533: Теорема PCP і складність апроксимації, восени 2005, короткий виклад Гурусвамі і О'Доннелла з Університету Вашингтону

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

[1] Johan Håstad. Some Optimal Inapproximability Results // Journal of the ACM. — 1999. — 3 листопада.

[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. — 6 жовтня.

[4] Subhash Khot, Oded Regev. Vertex cover might be hard to approximate to within 2-ε // IEEE Conference on Computational Complexity. — 2003. — 3 листопада. — С. 379–.