APX-klassen (fra engelsk "approximable") i teorien om beregningskompleksitet er en klasse af NP-hårde problemer, for hvilke der er tilnærmelsesalgoritmer af polynomisk kompleksitet med en konstant tilnærmelseskoefficient. I enklere vendinger har problemer af denne klasse effektive algoritmer, der finder løsninger, der er værre end optimale med ikke mere end en fast procentdel. For eksempel er der en polynomisk kompleksitetsalgoritme til løsning af containerpakningsproblemet , som ikke bruger mere end 5 % flere containere end det mindste antal containere, der kræves.
En tilnærmelsesalgoritme kaldes en c -tilnærmelsesalgoritme med en eller anden konstant c , hvis det kan bevises, at den opnåede løsning ved brug af denne algoritme ikke er mere end c gange værre end den optimale [1] .
Konstanten c kaldes tilnærmelsesfaktoren . Afhængig af om problemet er et maksimerings- eller minimeringsproblem, kan løsningen være c gange større eller c gange mindre end den optimale.
For eksempel har både toppunktsdækningsproblemet og det rejsende sælgerproblem med trekantsuligheden simple algoritmer, hvor c = 2 [2] . På den anden side er det blevet bevist, at det rejsende sælgerproblem med vilkårlige kantlængder (der ikke nødvendigvis opfylder trekantsuligheden) ikke kan tilnærmes med en konstant koefficient, da problemet med at finde en Hamiltonsk sti ikke kan løses i polynomisk tid (i tilfælde P ≠ NP ) [3] .
Hvis der er en algoritme til at løse et problem i polynomisk tid for en hvilken som helst fast koefficient større end én (én algoritme for en hvilken som helst koefficient), siges problemet at have et polynomisk-tidstilnærmelsesskema ( PTAS ) . Hvis P ≠ NP, kan det vises, at der er problemer, der er i APX -klassen, men ikke i PTAS , det vil sige problemer, der kan tilnærmes af en eller anden faktor, men ikke af en hvilken som helst faktor.
Et problem kaldes APX -hard, hvis ethvert problem fra APX -klassen kan reduceres til dette problem, og APX -complete, hvis problemet er APX - hardt og selv tilhører APX -klassen [1] . Uligheden P ≠ NP indebærer, at PTAS ≠ APX , P ≠ NP, og derfor hører intet APX - hårdt problem til PTAS .
Hvis problemet er APX -hårdt, er dette normalt dårligt, da det for P ≠ NP betyder, at der ikke er nogen PTAS -algoritme, som er den mest nyttige form for tilnærmelsesalgoritme. Et af de enkleste APX -komplette problemer er problemet med maksimal tilfredsstillelse for boolske formler , en variant af det boolske formeltilfredshedsproblem . I dette problem har vi en boolesk formel i konjunktiv normal form , og vi ønsker at få det maksimale antal underudtryk, der vil blive udført med en enkelt substitution af sande/falske værdier i variable. På trods af at problemet højst sandsynligt ikke tilhører PTAS , kan den korrekte værdi opnås med en nøjagtighed på 30 %, og nogle forenklede versioner af problemet har PTAS [4] [5] [6] .
| Kompleksitetsklasser af algoritmer | |
|---|---|
| Betragtes som lys | |
| Formodes at være svært | |
| Anses for vanskelig |
|