Czy istnieje jakiś szczególny problem z PSPACE, który ma algorytm FPTAS?

Dobrze wiadomo, że NP-Complete Problem o nazwie Subset Sum ma FPTAS. Zastanawiałem się, czy istnieje problem z PSPACE Complete, który ma także FPTAS? Z góry dziękuję.

ds.algorithms space-bounded big-picture Zelah 02
źródło

Myślę, że odpowiedź brzmi „nie”. 3-partycja nie dopuszcza FPTAS, ponieważ jest silnie NP-kompletna, chyba że P = NP. Ponadto istnieje zmniejszenie Karp z 3-partycji do dowolnego problemu związanego z PSPACE. Dlatego FPTAS dla dowolnego problemu pełnego PSPACE oznaczałby FPTAS dla 3-partycji, co jest niemożliwe, chyba że P = NP.

Mohammad Al-Turkistany

Redukcja karpia to redukcja zachowująca przybliżenie.

Mohammad Al-Turkistany

Nie rozumiem - dlaczego zachowuje przybliżenie redukcji Karp?

Peter Shor,

Redukcja karp jest zdefiniowana dla problemów decyzyjnych, każda redukcja zachowująca przybliżenie jest zdefiniowana dla problemów optymalizacyjnych. Dlatego redukcja Karp nie może być redukcją zachowującą przybliżenie.

Oleksandr Bondarenko

@Oleksandr, spójrz na to ( cs.tau.ac.il/~safra/Complexity/PCP.pdf )

Mohammad Al-Turkistany

Odpowiedzi:

Możliwe jest zdefiniowanie sztucznych problemów HARD PSPACE przy pomocy FPTAS: zdefiniuj gdzie jest boolowskim trudnym problemem PSPACE, którego złożoność wynosi co najwyżej , to jest również trudne dla PSPACE, ale ma FPTAS: jeśli to zwróć inaczej mamy wystarczająco dużo czasu na dokładne obliczenie . $f(x)=2^{|x|}+g(x)$ $g(x)$ $2^n$ $f$ $\epsilon \gt 2^{-|x|}$ $2^{|x|}$ $f$

Noam
źródło

Czy możesz podać konkretny (najlepiej naturalny) trudny PSPACE problem ze złożonością czasową ?

O (2^{n})

$O(2^n)$

Mohammad Al-Turkistany

TQBF wykona lewę - wejście: formuła logiczna f, wyjście: czy istnieje x1 tak, że dla wszystkich x2 istnieje x3, że dla wszystkich x4 istnieje ... istnieje xn takie, że f (x1 .... xn).

Noam