Ist APX in NP enthalten?

15

Es wird gesagt, dass ein Problem P in APX vorliegt, wenn eine Konstante c> 0 existiert, so dass ein Polynomzeit-Approximationsalgorithmus für P mit einem Approximationsfaktor von 1 + c existiert.

APX enthält PTAS (durch einfaches Auswählen einer beliebigen Konstanten c> 0) und P.

Ist APX in NP? Bedeutet die Existenz eines Polynom-Zeit-Näherungsalgorithmus für einen Näherungsfaktor insbesondere, dass das Problem in NP liegt?

cc.complexity-theory complexity-classes apx Andrew W.
quelle
Ich denke, "was über Klasse X im Vergleich zu allen anderen Klassen Y bekannt ist" ist als Frage viel zu vage, es sei denn, es werden einige weitere Einzelheiten zu den Arten der gesuchten Beziehungen angegeben.
András Salamon
Ich meine Beziehungen wie 'enthält', 'ist enthalten in', 'enthält nicht'.
Andrew W.
Nach einigem Nachdenken habe ich die Frage auf die Beziehung eingegrenzt, die mich am meisten interessiert.
Andrew W.
1
Was genau bedeutet es zu fragen, ob APX in NP enthalten ist? APX besteht aus approximierbaren "NP-Optimierungs" -Problemen, während NP aus Entscheidungsproblemen besteht. Außerdem ist per Definition die Entscheidungsversion eines NP-Optimierungsproblems in NP. Vielleicht hatten Sie etwas anderes im Sinn?
Joshua Grochow
Du hast recht Joshua. Ian beantwortete die Frage, die ich hätte stellen sollen.
Andrew W.

Antworten:

20

APX ist als Teilmenge von NPO definiert. Wenn also ein Optimierungsproblem in APX vorliegt, liegt das entsprechende Entscheidungsproblem in NP.

Wenn Sie jedoch fragen, ob ein beliebiges Problem in NP (oder NPO) vorliegen muss, wenn es eine Poly-Time-O (1) -Näherung gibt, lautet die Antwort Nein. Ich kenne keine natürlichen Probleme, die als Gegenbeispiel dienen, aber man könnte ein künstliches Maximierungsproblem definieren, bei dem das Ziel die Summe zweier Terme ist, ein großer Term, der in P leicht optimiert werden kann, und ein viel kleinerer Term Das fügt eine kleine Menge hinzu, wenn ein Teil der Lösung eine Antwort auf ein schwieriges Problem (außerhalb von NP) codiert. Dann könnte man beispielsweise eine 2-Approximation in Polyzeit finden, indem man sich auf den einfachen Term konzentriert, aber um eine optimale Lösung zu finden, müsste das schwierige Problem gelöst werden.

Ian
quelle
2
Ich habe Ihre Antwort akzeptiert, weil sie sowohl die von mir gestellte Frage ('Ist APX in NP enthalten?') Als auch die Frage, die ich hätte stellen sollen ('Bedeutet eine Poly-Zeit-O (1) ungefähr eine exakte Lösung in NP?') Beantwortet.
Andrew W.
1
Eine breite Klasse von Problemen , die in NPO und NP enthalten sind , nicht aber konstante Faktor Approximation haben , ist die Klasse der Online - Probleme (die Frage auf , was ist hier online Probleme Komplexitätsklasse enthält cstheory.stackexchange.com/questions/1664/... ) .
Oleksandr Bondarenko