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

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

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

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

Історія

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

Приклади

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

Див. також

• PCP-теорема
• Гіпотеза про ігри з єдиною відповіддю^[en]