Třída APX (z anglického „approximable“) v teorii výpočetní složitosti je třída NP-těžkých problémů , pro které existují aproximační algoritmy polynomiální složitosti s konstantním koeficientem aproximace. Jednodušeji řečeno, problémy této třídy mají účinné algoritmy, které nalézají řešení, která jsou horší než optimální o ne více než pevné procento. Například existuje algoritmus polynomiální složitosti pro řešení problému s balením kontejnerů , který nepoužívá o více než 5 % více kontejnerů, než je nejmenší požadovaný počet kontejnerů.
Aproximační algoritmus se nazývá c -aproximační algoritmus s nějakou konstantou c , pokud lze dokázat, že řešení získané pomocí tohoto algoritmu není více než ckrát horší než optimální [1] .
Konstanta c se nazývá aproximační faktor . V závislosti na tom, zda se jedná o problém maximalizace nebo minimalizace, může být řešení ckrát větší nebo ckrát menší než optimální.
Například problém pokrytí vrcholů i problém obchodního cestujícího s trojúhelníkovou nerovností mají jednoduché algoritmy, pro které c = 2 [2] . Na druhou stranu bylo prokázáno, že problém obchodního cestujícího s libovolnými délkami hran (nemusí nutně splňovat trojúhelníkovou nerovnost) nelze aproximovat konstantním koeficientem, protože problém hledání hamiltonovské cesty nelze vyřešit v polynomiálním čase (v případ P ≠ NP ) [3] .
Pokud existuje algoritmus pro řešení problému v polynomiálním čase pro jakýkoli pevný koeficient větší než jedna (jeden algoritmus pro jakýkoli koeficient), říká se, že problém má schéma polynomiální časové aproximace ( PTAS ) . Pokud P ≠ NP, lze ukázat, že existují problémy, které jsou ve třídě APX , ale ne v PTAS , tedy problémy, které lze aproximovat nějakým faktorem, ale ne žádným faktorem.
Problém se nazývá APX -hard, pokud lze jakýkoli problém z třídy APX zredukovat na tento problém, a APX -complete, pokud je problém APX -hard a sám patří do třídy APX [1] . Nerovnice P ≠ NP znamená, že PTAS ≠ APX , P ≠ NP, a tedy žádný APX -těžký problém nepatří k PTAS .
Pokud je problém APX -těžký, je to obvykle špatné, protože pro P ≠ NP to znamená, že neexistuje žádný PTAS -algoritmus, což je nejužitečnější druh aproximačního algoritmu. Jedním z nejjednodušších APX - úplných problémů je problém maximální splnitelnosti pro booleovské vzorce , varianta problému splnitelnosti booleovských vzorců . V tomto problému máme booleovský vzorec v konjunktivním normálním tvaru a chceme získat maximální počet podvýrazů, které budou provedeny s jedinou substitucí hodnot true/false v proměnných. Navzdory tomu, že problém s největší pravděpodobností nepatří do PTAS , správnou hodnotu lze získat s přesností 30 % a některé zjednodušené verze problému mají PTAS [4] [5] [6] .
| Třídy složitosti algoritmů | |
|---|---|
| Považováno za světlo | |
| Prý to bude těžké | |
| Považováno za obtížné |
|