¿Existe un problema completo de PSPACE en particular que tenga un algoritmo FPTAS?

Es bien sabido que el problema NP-Complete llamado Subset Sum tiene un FPTAS. Me preguntaba si existía un problema PSPACE Complete que también tiene un FPTAS. Gracias por adelantado.

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

Supongo que la respuesta sería no. La partición 3 no admite FPTAS ya que está fuertemente completa NP a menos que P = NP. Además, hay una reducción de Karp de 3 particiones a cualquier problema de competencia de PSPACE. Por lo tanto, FPTAS para cualquier problema de PSPACE completo implicaría FPTAS para 3 particiones, lo cual es imposible a menos que P = NP.

Mohammad Al-Turkistany

La reducción de Karp es una reducción de preservación de aproximación.

Mohammad Al-Turkistany

No entiendo: ¿por qué la reducción de Karp preserva la aproximación?

Peter Shor

La reducción de Karp se define para problemas de decisión, cualquiera de las reducciones de preservación de aproximación se define para problemas de optimización. Por lo tanto, la reducción de Karp no puede ser una reducción que conserve la aproximación.

Oleksandr Bondarenko

@Oleksandr, Echa un vistazo a esto ( cs.tau.ac.il/~safra/Complexity/PCP.pdf )

Mohammad Al-Turkistany

Respuestas:

Es posible definir problemas artificiales de PSPACE-HARD con un FPTAS: defina donde es un problema booleano difícil de PSPACE cuya complejidad es como máximo , entonces también es difícil de PSPACE, pero tiene un FPTAS: si luego regrese de lo contrario, tenemos tiempo suficiente para calcular exactamente. $f(x)=2^{|x|}+g(x)$ $g(x)$ $2^n$ $f$ $\epsilon \gt 2^{-|x|}$ $2^{|x|}$ $f$

Noam
fuente

¿Podría dar un problema específico (preferiblemente natural) difícil de PSPACE con la complejidad del tiempo

O (2^{n})

$O(2^n)$

Mohammad Al-Turkistany

TQBF haría el truco: entrada: fórmula booleana f, salida: ¿existe x1 tal que para todo x2 existe x3 que para todo x4 existe ... existe xn tal que f (x1 .... xn).

Noam