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

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