У математиці схема наближення до поліноміального часу (СНПЧ або PTAS від англ. polynomial-time approximation scheme) — клас наближених до поліноміальних за часом виконання алгоритмів для розв'язування, як правило, NP-складних оптимізаційних задач. Якщо P = NP, то впровадження цього поняття втрачає сенс. Тому далі припускатимемо, що Р не збігається з NP. І, без обмеження загальності, визначимо поняття для задачі мінімізації.
Визначення
СНПЧ це сімейство алгоритмів, які залежать від параметра ε , таких, що для довільного набору даних деякої оптимізаційної задачі та параметра ε > 0 алгоритм сімейства за поліноміальний час знаходить розв'язок із цільовою функцією S<(1 + ε)OPT, де OPT — мінімум цільової функції. Наприклад, для задачі комівояжера в евклідовому просторі існує СНПЧ, яка знаходить шлях обходу довжини не більше (1 + ε)L, де L — довжина найкоротшого шляху[1].
Час виконання СНПЧ має поліноміально залежати від n за будь-якого фіксованого ε, але може довільно змінюватися при зміні ε. Алгоритми з часом виконання O(n1/ε) або навіть O(nexp(1/ε)) є алгоритмами СНПЧ.
Детерміновані алгоритми
В алгоритмах СНПЧ показник степеня в оцінці складності може зростати катастрофічно при спаданні ε, наприклад, коли час виконання O(n(1/ε)!), що робить цей клас алгоритмів малоцікавим із практичної точки зору. Можна визначити ефективну схему наближення до поліноміального часу (ЕСНПЧ або EPTAS від англ. efficient polynomial-time approximation scheme), для якої час виконання має бути O(nc), де константа c не залежить від ε. Це гарантує, що збільшення вхідних даних збільшує час виконання незалежно від величини ε; однак множник під знаком O, при цьому продовжує довільно залежати від ε. Подальшим корисним обмеженням є схема повного наближення до поліноміального часу (СПНПЧ або FPTAS від англ. fully polynomial-time approximation scheme), яка вимагає, щоб час виконання алгоритму поліноміально залежав і від розміру задачі n, і від 1/ε. Прикладом задачі для якої існує СПНПЧ є задача про рюкзак. Але для спорідненої задачі про пакування в ємності немає навіть СНПЧ.
Будь-яка сильно NP-складна задача оптимізації з поліноміально обмеженою цільовою функцією не може мати СПНПЧ[2]. Проте зворотне хибне. Двовимірна задача про ранець не є сильно NP-складною, але не має СПНПЧ навіть, коли цільова функція поліноміально обмежена[3].
Виконується СПНПЧ ⊊ СНПЧ ⊊ APX. Отже, APX-складні задачі не мають СНПЧ.
Іншою модифікацією СНПЧ є схема наближення до квазі-поліноміального часу (СНКПЧ або QPTAS від англ. quasi-polynomial-time approximation scheme). СНКПЧ має часову складність 
для будь-якого фіксованого 
.
Увипадковлені алгоритми
Деякі задачі, які не мають СНПЧ, можуть мати увипадковлені алгоритми з подібними властивостями — увипадковлену схему наближення до поліноміального часу (УСНПЧ або PRAS від англ. polynomial-time randomized approximation scheme). Алгоритм УСНПЧ з параметром ε > 0 для довільного набору даних оптимізаційної задачі знаходить за поліноміальний час розв'язок, який з високою ймовірністю не перевищує (1 + ε)OPT. Зазвичай під «високою ймовірністю» розуміють ймовірність більше 3/4, хоча у визначенні цю величину не конкретизовано. Як і алгоритм СНПЧ алгоритм УСНПЧ повинен мати час виконання, що поліноміально залежить від n, але не від 1/ε. За аналогією з детермінованими алгоритмами уводяться ЕУСНПЧ (EPRAS), подібна до ЕСНПЧ, і УСПНПЧ (FPRAS), подібна до СПНПЧ[2].
Примітки
- ↑ Санджив Арора[en], Polynomial-time Approximation Schemes for Euclidean TSP and other Geometric Problems, Journal of the ACM 45(5) 753—782, 1998.
- ↑ а б Vazirani, Vijay V. Approximation Algorithms. — Berlin : Springer, 2003. — С. 294—295. — ISBN 3-540-65367-8.
- ↑ H. Kellerer and U. Pferschy and D. Pisinger. Knapsack Problems. — Springer, 2004.
Посилання
