APX

För annan användning, se APX (disambiguation) .

I beräkningskomplexitetsteori är klassen APX (en förkortning av "approximable") uppsättningen av NP- optimeringsproblem som tillåter polynom-tidsapproximationsalgoritmer med approximationsförhållande som begränsas av en konstant (eller förkortat approximationsalgoritmer med konstant faktor) . Enkelt uttryckt har problem i den här klassen effektiva algoritmer som kan hitta ett svar inom någon fast multiplikativ faktor för det optimala svaret.

En approximationsalgoritm kallas en $f(n)$ -approximationsalgoritm för indatastorlek $n$ om det kan bevisas att lösningen som algoritmen hittar är högst en multiplikationsfaktor av $f(n)$ gånger sämre än den optimala lösningen. Här kallas ${\displaystyle f(n)} för$ approximationsförhållandet . Problem i APX är de med algoritmer där approximationsförhållandet $f(n)$ är en konstant $c$ . Approximationsförhållandet anges konventionellt större än 1. I fallet med minimeringsproblem $f(n)$ den hittade lösningens poäng dividerat med den optimala lösningens poäng, medan för maximeringsproblem är det omvända fallet . För maximeringsproblem, där en sämre lösning har en mindre poäng, anges ibland ${\displaystyle f(n)} som mindre än 1;$ i sådana fall är den reciproka av $f(n)$ förhållandet mellan poängen för den hittade lösningen och poängen för den optimala lösningen.

Ett problem sägs ha ett polynom-tidsapproximationsschema ( PTAS ) om det för varje multiplikativ faktor av det optimala sämre än 1 finns en polynom-tidsalgoritm för att lösa problemet inom den faktorn. Såvida inte P = NP finns det problem som finns i APX men utan en PTAS, så klassen av problem med en PTAS finns strikt i APX. Ett sådant problem är packningsproblemet .

APX-hårdhet och APX-fullständighet

Ett problem sägs vara APX-hårt om det finns en PTAS-reduktion från varje problem i APX till det problemet, och vara APX-komplett om problemet är APX-hårt och även i APX. Som en konsekvens av P ≠ NP ⇒ PTAS ≠ APX, om P ≠ NP antas, har inget APX-hårt problem en PTAS. I praktiken görs att reducera ett problem till ett annat för att visa APX-fullständighet ofta med andra reduktionsscheman, såsom L-reduktioner , som innebär PTAS-reduktioner.

Exempel

Ett av de enklaste APX-komplettproblemen är MAX-3SAT-3, en variant av det booleska tillfredsställbarhetsproblemet . I det här problemet har vi en boolesk formel i konjunktiv normal form där varje variabel förekommer högst 3 gånger, och vi vill veta det maximala antalet satser som samtidigt kan uppfyllas genom en enda tilldelning av sanna/falska värden till variablerna.

Andra problem med APX-komplett inkluderar:

• Max oberoende uppsättning i grafer med begränsade grader (här beror approximationsförhållandet på grafens maximala grad, men är konstant om maxgraden är fast).
• Min vertexskydd . Komplementet av varje maximalt oberoende set måste vara ett vertextäcke.
• Min dominerande set i grafer med avgränsade grader.
• resande försäljare när avstånden i grafen uppfyller villkoren för ett mått . TSP är NPO-komplett i det allmänna fallet.
• Token -omkonfigurationsproblemet , via L-reduktion från setlocket.

Relaterade komplexitetsklasser

PTAS

Huvudartikel: Polynom-tidsapproximationsschema

PTAS ( polynomial time approximation scheme ) består av problem som kan approximeras till inom vilken konstant faktor som helst förutom 1 i tid som är polynom i förhållande till indatastorleken, men polynomet beror på en sådan faktor. Denna klass är en delmängd av APX.

APX-mellan

Om inte P = NP finns det problem i APX som varken är i PTAS eller APX-komplett. Sådana problem kan tänkas ha en hårdhet mellan PTAS-problem och APX-kompletta problem, och kan kallas APX-intermediate . Papperspackningsproblemet tros vara APX-mellanliggande . Trots att det inte har en känd PTAS, har binpackningsproblemet flera "asymptotiska PTAS"-algoritmer, som beter sig som en PTAS när den optimala lösningen är stor, så intuitivt kan det vara lättare än problem som är APX-hårda.

Ett annat exempel på ett potentiellt APX-mellanliggande problem är min kantfärgning .

f(n)-APX

Man kan också definiera en familj av komplexitetsklasser $f(n)$ -APX, där $f(n)$ -APX innehåller problem med en polynomisk tidsapproximationsalgoritm med ett $O(f(n))$ approximationsförhållande. Man kan analogt definiera $f(n)$ -APX-kompletta klasser; vissa sådana klasser innehåller välkända optimeringsproblem. Log-APX-fullständighet och poly-APX-fullständighet definieras i termer av AP-reduktioner snarare än PTAS-reduktioner; detta beror på att PTAS-reduktioner inte är tillräckligt starka för att behålla medlemskapet i Log-APX och Poly-APX, även om de räcker för APX.

Log-APX-komplett, som består av de svåraste problemen som effektivt kan approximeras inom en faktorlogaritmisk indatastorlek, inkluderar min dominerande uppsättning när graden är obegränsad.

Poly-APX-komplett, bestående av de svåraste problemen som effektivt kan approximeras inom ett faktorpolynom i indatastorleken, inkluderar max oberoende uppsättning i det allmänna fallet.

Det finns också problem som är exp-APX-kompletta, där approximationsförhållandet är exponentiellt i indatastorleken. Detta kan inträffa när approximationen är beroende av värdet på siffror i probleminstansen; dessa tal kan uttryckas i rymdlogaritmiskt värde, därav exponentialfaktorn.

Se även

• Approximationsbevarande reduktion
• Komplexitetsklass
• Approximationsalgoritm
• Max/min CSP/Ones klassificeringssatser - en uppsättning satser som möjliggör mekanisk klassificering av problem om booleska relationer i approximationskomplexitetsklasser
• MaxSNP - en närbesläktad underklass

• Komplexitet Zoo : APX
• C. Papadimitriou och M. Yannakakis. Optimerings-, approximations- och komplexitetsklasser . Journal of Computer and System Sciences, 43:425–440, 1991.
• Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski och Gerhard Woeginger . Maximal Satisfiability Arkiverad 2007-04-13 på Wayback Machine . Ett kompendium med NP-optimeringsproblem Arkiverad 2007-04-05 på Wayback Machine .