Clasa APX (din limba engleză „aproximable”) în teoria complexității computaționale este o clasă de probleme NP-hard pentru care există algoritmi de aproximare de complexitate polinomială cu un coeficient de aproximare constant. În termeni mai simpli, problemele acestei clase au algoritmi eficienți care găsesc soluții mai proaste decât optime cu cel mult un procent fix. De exemplu, există un algoritm de complexitate polinomială pentru rezolvarea problemei de ambalare a containerelor care utilizează nu mai mult de 5% mai multe containere decât cel mai mic număr de containere necesar.
Un algoritm de aproximare se numește c -algoritm de aproximare cu o constantă c dacă se poate demonstra că soluția obținută folosind acest algoritm este de nu mai mult de c ori mai proastă decât cea optimă [1] .
Constanta c se numește factor de aproximare . În funcție de faptul că problema este o problemă de maximizare sau de minimizare, soluția poate fi de c ori mai mare sau de c ori mai mică decât cea optimă.
De exemplu, atât problema acoperirii vârfurilor cât și problema vânzătorului ambulant cu inegalitatea triunghiului au algoritmi simpli pentru care c = 2 [2] . Pe de altă parte, s-a dovedit că problema vânzătorului ambulant cu lungimi arbitrare de muchii (care nu satisface neapărat inegalitatea triunghiului) nu poate fi aproximată cu un coeficient constant, deoarece problema găsirii unei căi hamiltoniene nu poate fi rezolvată în timp polinomial (în cazul P ≠ NP ) [3] .
Dacă există un algoritm pentru rezolvarea unei probleme în timp polinomial pentru orice coeficient fix mai mare de unu (un algoritm pentru orice coeficient), se spune că problema are o schemă de aproximare în timp polinomial ( PTAS ) . Dacă P ≠ NP, se poate arăta că există probleme care sunt în clasa APX dar nu și în PTAS , adică probleme care pot fi aproximate de un anumit factor, dar nu de orice factor.
O problemă se numește APX -hard dacă orice problemă din clasa APX poate fi redusă la această problemă, iar APX -complete dacă problema este APX -hard și aparține ea însăși clasei APX [1] . Inegalitatea P ≠ NP implică faptul că PTAS ≠ APX , P ≠ NP și, prin urmare, nicio problemă APX -hard nu aparține PTAS .
Dacă problema este APX -hard, acest lucru este de obicei rău, deoarece pentru P ≠ NP înseamnă că nu există un algoritm PTAS , care este cel mai util tip de algoritm de aproximare. Una dintre cele mai simple probleme APX - complete este problema de satisfacție maximă pentru formulele booleene , o variantă a problemei de satisfacție a formulei booleene . În această problemă, avem o formulă booleană în formă normală conjunctivă și dorim să obținem numărul maxim de subexpresii care vor fi executate cu o singură înlocuire a valorilor adevărat/fals în variabile. În ciuda faptului că problema cel mai probabil nu aparține PTAS , valoarea corectă poate fi obținută cu o precizie de 30%, iar unele versiuni simplificate ale problemei au PTAS [4] [5] [6] .
| Clasele de complexitate ale algoritmilor | |
|---|---|
| Considerată ușoară | |
| Ar trebui să fie dificil | |
| Considerat dificil |
|