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

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

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

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

Історія

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

Приклади

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

Див. також

PCP-теорема
^[en]

Примітки

Johan Håstad. Some Optimal Inapproximability Results // Journal of the ACM. — 1999. — 16 червня.
Subhash Khot. Proceedings of the thirty-fourth annual ACM symposium on Theory of computing. — 2002. — С. 767–775. — . — 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. — 16 червня. — С. 379–.

Література

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

Посилання

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

[1] Johan Håstad. Some Optimal Inapproximability Results // Journal of the ACM. — 1999. — 16 червня.

[2] Subhash Khot. Proceedings of the thirty-fourth annual ACM symposium on Theory of computing. — 2002. — С. 767–775. — . — 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. — 16 червня. — С. 379–.