Схема наближення до поліноміального часу

У математиці схема наближення до поліноміального часу (СНПЧ або PTAS від англ. polynomial-time approximation scheme) — клас наближених до поліноміальних за часом виконання алгоритмів для розв'язування, як правило, NP-складних оптимізаційних задач. Якщо P = NP, то впровадження цього поняття втрачає сенс. Тому далі припускатимемо, що Р не збігається з NP. І, без обмеження загальності, визначимо поняття для задачі мінімізації.

Визначення

СНПЧ це сімейство алгоритмів, які залежать від параметра ε , таких, що для довільного набору даних деякої оптимізаційної задачі та параметра ε > 0 алгоритм сімейства за поліноміальний час знаходить розв'язок із цільовою функцією S<(1 + ε)OPT, де OPT — мінімум цільової функції. Наприклад, для задачі комівояжера в евклідовому просторі існує СНПЧ, яка знаходить шлях обходу довжини не більше (1 + ε)L, де L — довжина найкоротшого шляху^[1].

Час виконання СНПЧ має поліноміально залежати від n за будь-якого фіксованого ε, але може довільно змінюватися при зміні ε. Алгоритми з часом виконання O(n^1/ε) або навіть O(n^exp(1/ε)) є алгоритмами СНПЧ.

Детерміновані алгоритми

В алгоритмах СНПЧ показник степеня в оцінці складності може зростати катастрофічно при спаданні ε, наприклад, коли час виконання O(n^(1/ε)!), що робить цей клас алгоритмів малоцікавим із практичної точки зору. Можна визначити ефективну схему наближення до поліноміального часу (ЕСНПЧ або EPTAS від англ. efficient polynomial-time approximation scheme), для якої час виконання має бути O(n^c), де константа c не залежить від ε. Це гарантує, що збільшення вхідних даних збільшує час виконання незалежно від величини ε; однак множник під знаком O, при цьому продовжує довільно залежати від ε. Подальшим корисним обмеженням є схема повного наближення до поліноміального часу (СПНПЧ або FPTAS від англ. fully polynomial-time approximation scheme), яка вимагає, щоб час виконання алгоритму поліноміально залежав і від розміру задачі n, і від 1/ε. Прикладом задачі для якої існує СПНПЧ є задача про рюкзак. Але для спорідненої задачі про пакування в ємності немає навіть СНПЧ.

Будь-яка сильно NP-складна задача оптимізації з поліноміально обмеженою цільовою функцією не може мати СПНПЧ^[2]. Проте зворотне хибне. Двовимірна задача про ранець не є сильно NP-складною, але не має СПНПЧ навіть, коли цільова функція поліноміально обмежена^[3].

Виконується СПНПЧ ⊊ СНПЧ ⊊ APX. Отже, APX-складні задачі не мають СНПЧ.

Іншою модифікацією СНПЧ є схема наближення до квазі-поліноміального часу (СНКПЧ або QPTAS від англ. quasi-polynomial-time approximation scheme). СНКПЧ має часову складність ${\displaystyle n^{polylog(n)}}$ для будь-якого фіксованого ${\displaystyle \epsilon >0}$.

Увипадковлені алгоритми

Деякі задачі, які не мають СНПЧ, можуть мати увипадковлені алгоритми з подібними властивостями — увипадковлену схему наближення до поліноміального часу (УСНПЧ або PRAS від англ. polynomial-time randomized approximation scheme). Алгоритм УСНПЧ з параметром ε > 0 для довільного набору даних оптимізаційної задачі знаходить за поліноміальний час розв'язок, який з високою ймовірністю не перевищує (1 + ε)OPT. Зазвичай під «високою ймовірністю» розуміють ймовірність більше 3/4, хоча у визначенні цю величину не конкретизовано. Як і алгоритм СНПЧ алгоритм УСНПЧ повинен мати час виконання, що поліноміально залежить від n, але не від 1/ε. За аналогією з детермінованими алгоритмами уводяться ЕУСНПЧ (EPRAS), подібна до ЕСНПЧ, і УСПНПЧ (FPRAS), подібна до СПНПЧ^[2].

Примітки

1. Санджив Арора^[en], Polynomial-time Approximation Schemes for Euclidean TSP and other Geometric Problems, Journal of the ACM 45(5) 753—782, 1998.
2. Vazirani, Vijay V. Approximation Algorithms. — Berlin : Springer, 2003. — С. 294—295. — ISBN 3-540-65367-8.
3. H. Kellerer and U. Pferschy and D. Pisinger. Knapsack Problems. — Springer, 2004.

Посилання

• Зоопарк сложностей: PTAS, EPTAS, FPTAS
• Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski, and Gerhard Woeginger, A compendium of NP optimization problems — список NP-складних задач оптимізації, які мають СНПЧ. Архівовано жовтень 2, 2013 на сайті Wayback Machine.