APX-klassen (från engelskan "approximable") i teorin om beräkningskomplexitet är en klass av NP-hårda problem för vilka det finns approximationsalgoritmer med polynomkomplexitet med en konstant approximationskoefficient. I enklare termer har problem av denna klass effektiva algoritmer som hittar lösningar som är sämre än optimala med inte mer än en fast procentandel. Till exempel finns det en polynomkomplexitetsalgoritm för att lösa behållarpackningsproblemet som inte använder mer än 5 % fler behållare än det minsta antal behållare som behövs.
En approximationsalgoritm kallas en c -approximationsalgoritm med någon konstant c om det kan bevisas att lösningen som erhålls med denna algoritm inte är mer än c gånger sämre än den optimala [1] .
Konstanten c kallas approximationsfaktorn . Beroende på om problemet är ett maximerings- eller minimeringsproblem kan lösningen vara c gånger större eller c gånger mindre än den optimala.
Till exempel har både vertextäckningsproblemet och resandeförsäljarproblemet med triangelolikheten enkla algoritmer för vilka c = 2 [2] . Å andra sidan har det bevisats att det resande säljarproblemet med godtyckliga kantlängder (som inte nödvändigtvis uppfyller triangelolikheten) inte kan approximeras med en konstant koefficient, eftersom problemet med att hitta en Hamiltonsk väg inte kan lösas i polynomtid (i fall P ≠ NP ) [3] .
Om det finns en algoritm för att lösa ett problem i polynomtid för någon fast koefficient som är större än en (en algoritm för vilken koefficient som helst), sägs problemet ha ett polynom-tidsapproximationsschema ( PTAS ) . Om P ≠ NP kan det visas att det finns problem som är i APX -klassen men inte i PTAS , det vill säga problem som kan approximeras av någon faktor, men inte av någon faktor.
Ett problem kallas APX -hårt om något problem från APX -klassen kan reduceras till detta problem, och APX -komplett om problemet är APX -hårt och i sig tillhör APX -klassen [1] . Ojämlikheten P ≠ NP innebär att PTAS ≠ APX , P ≠ NP, och därför hör inget APX -hårt problem till PTAS .
Om problemet är APX -hårt är detta vanligtvis dåligt, eftersom det för P ≠ NP betyder att det inte finns någon PTAS -algoritm, vilket är den mest användbara typen av approximationsalgoritm. Ett av de enklaste APX -komplettproblemen är problemet med maximal tillfredsställelse för booleska formler , en variant av det booleska formelns tillfredsställelseproblem . I det här problemet har vi en boolesk formel i konjunktiv normal form , och vi vill få det maximala antalet underuttryck som kommer att exekveras med en enda substitution av sanna/falska värden i variabler. Trots att problemet med största sannolikhet inte tillhör PTAS , kan det korrekta värdet erhållas med en noggrannhet på 30 %, och vissa förenklade versioner av problemet har PTAS [4] [5] [6] .
| Komplexitetsklasser av algoritmer | |
|---|---|
| Anses som ljus | |
| Ska vara svårt | |
| Anses vara svårt |
|