Gibt es ein bestimmtes PSPACE Complete-Problem mit einem FPTAS-Algorithmus?

Es ist bekannt, dass das NP-vollständige Problem namens Subset Sum ein FPTAS hat. Ich habe mich gefragt, ob es ein PSPACE Complete-Problem gibt, das auch ein FPTAS hat. Danke im Voraus.

ds.algorithms space-bounded big-picture Zelah 02
quelle

Ich denke die Antwort wäre nein. 3-Partition lässt FPTAS nicht zu, da es stark NP-vollständig ist, es sei denn, P = NP. Außerdem gibt es eine Karp-Reduzierung von 3 Partitionen auf jedes PSPACE-Konkurrenzproblem. Daher würde FPTAS für jedes PSPACE-vollständige Problem FPTAS für 3-Partitionen implizieren, was unmöglich ist, wenn nicht P = NP.

Mohammad Al-Turkistany

Die Karp-Reduktion ist eine approximationserhaltende Reduktion.

Mohammad Al-Turkistany

Ich verstehe nicht - warum bleibt die Annäherung an die Karp-Reduktion erhalten?

Peter Shor

Die Karp-Reduktion ist für Entscheidungsprobleme definiert, jede der approximationserhaltenden Reduktionen ist für Optimierungsprobleme definiert. Daher kann die Karp-Reduktion keine approximationserhaltende Reduktion sein.

Oleksandr Bondarenko

@Oleksandr, Schauen Sie sich das an ( cs.tau.ac.il/~safra/Complexity/PCP.pdf )

Mohammad Al-Turkistany

Antworten:

Mit einem FPTAS können künstliche PSPACE-HARD-Probleme definiert werden: definiere wobei ein boolesches PSPACE-hartes Problem ist, dessen Komplexität höchstens beträgt , dann ist auch PSPACE-hart, hat aber ein FPTAS: wenn dann sonst haben wir genug Zeit, um genau zu berechnen . $f(x)=2^{|x|}+g(x)$ $g(x)$ $2^n$ $f$ $\epsilon \gt 2^{-|x|}$ $2^{|x|}$ $f$

Noam
quelle

Könnten Sie ein spezifisches (vorzugsweise natürliches) PSPACE-hartes Problem mit

Zeitkomplexität angeben?

O (2^{n})

$O(2^n)$

Mohammad Al-Turkistany

TQBF würde den Trick machen - Eingabe: Boolesche Formel f, Ausgabe: Existiert x1 so, dass für alle x2 x3 existiert, dass für alle x4 existiert ... existiert xn so, dass f (x1 .... xn).

Noam