Bedeutet PSPACE-Vollständigkeit eine Approximationshärte?

14

In einem Kommentar in einem anderen cstheorySE-Post wird erwähnt, dass PSPACE-Vollständigkeit APX-Härte impliziert. Kann jemand bitte eine Referenz dafür erklären / teilen?

Ist das "eng"? (dh gibt es PSPACE-vollständige Probleme, deren Optimierungsproblem eine konstante Faktorapproximation in Polyzeit zulässt?)

Was ist mit der Vollständigkeit für ein bestimmtes PH-Niveau? Bedeutet dies eine Näherungshärte?

cc.complexity-theory approximation-algorithms approximation-hardness np pspace RB
quelle
2
Siehe arxiv.org/pdf/math/9409225.pdf
Saeed
4
Dieses Papier scheint PTAS-Ergebnisse für PSPACE-vollständige Probleme zu liefern
Sasho Nikolov
4
Das war ein schlechter Kommentar. Die Idee war, eine heuristische Vermutung anzustellen. Tut mir leid, wenn es sich um eine Tatsachenfeststellung handelte! Eine ist eine Klasse von Entscheidungsproblemen und eine Klasse von Funktionsproblemen, daher ist die Aussage nicht einmal genau definiert. Ich denke, die Überlegung war nur, dass Sie ein Problem in APX genau unter Verwendung des Polynomraums beantworten können. Aber es würde einige Arbeit erfordern, um die Verbindung zu formalisieren, und ich bezog mich nicht auf irgendwelche formalen Ergebnisse, von denen ich wusste.
USUL
1
Die beiden Ideen scheinen ziemlich verschieden zu sein. Vermutlich kann die Zielfunktion für die meisten Probleme zu modifiziert werden, wobei eine Obergrenze für die Werte ist, die praktikable Lösungen annehmen kann. ist dann immer noch genau so schwer zu berechnen wie , hat aber trivialerweise einen (oder sogar ) Approximationsalgorithmus, wenn es eine praktikable Lösung gibt. Dieses Argument sollte für Klassen sogar "härter" als PSPACE-complete sein. f(x)f^(x)=f(x)+nkkff^f(1-ϵ)(1-1/n)
Yonatan N
Wenn ich mich richtig erinnere, sind APX nur für NP-Optimierungsprobleme definiert? dh APX NP-Optimierung. Wenn wir über PSPACE-Complete sprechen, sind wir dann nicht schon jenseits des Definitionsregimes? ⊆
Stupid_Guy

Antworten:

2

Da es noch keine Antwort gibt, möchte ich antworten, Marathe et al. In ihrer ICALP93-Veröffentlichung haben sie einige Probleme definiert, die PSPACE-vollständig sind, aber konstante Faktor-Approximationen zulassen. Außerdem liefern sie einige Unannäherungsergebnisse. Betrachten Sie für diese spezielle Frage MAX3SAT. Das entsprechende Entscheidungsproblem ist PSPACE-vollständig, auch wenn der entsprechende SAT-Graph eine hierarchische Struktur aufweist, wie sie in ihrem Artikel definiert wurde. Dieses Problem weist jedoch einen 2-Approximations-Garantiealgorithmus in hierarchischer Struktur auf.

Saeed
quelle