Existe um determinado problema completo do PSPACE que possui um algoritmo FPTAS?

É sabido que o problema NP-Complete chamado Subset Sum possui um FPTAS. Gostaria de saber se existe um problema PSPACE Complete que também possui um FPTAS? Desde já, obrigado.

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

Eu acho que a resposta seria não. A partição 3 não admite FPTAS, pois é fortemente concluída em NP, a menos que P = NP. Além disso, há uma redução de Karp de 3 partições para qualquer problema de competição do PSPACE. Portanto, o FPTAS para qualquer problema de PSPACE completo implicaria o FPTAS para 3 partições, o que é impossível, a menos que P = NP.

Mohammad Al-Turkistany

A redução de Karp é uma redução de preservação de aproximação.

Mohammad Al-Turkistany

Eu não entendo - por que a redução de Karp preserva a aproximação?

Peter Shor

A redução de Karp é definida para problemas de decisão, qualquer uma das reduções de preservação de aproximação é definida para problemas de otimização. Portanto, a redução de Karp não pode ser uma redução de preservação de aproximação.

Oleksandr Bondarenko

@Oleksandr, Dê uma olhada nisto ( cs.tau.ac.il/~safra/Complexity/PCP.pdf ) #

Mohammad Al-Turkistany

Respostas:

É possível definir problemas artificiais do PSPACE-HARD com um FPTAS: defina que é um problema booleano do PSPACE cuja complexidade é no máximo , então também é difícil para o PSPACE, mas possui um FPTAS: se seguida, retorne contrário, temos tempo suficiente para calcular exatamente. $f(x)=2^{|x|}+g(x)$ $g(x)$ $2^n$ $f$ $\epsilon \gt 2^{-|x|}$ $2^{|x|}$ $f$

Noam
fonte

Você poderia dar um problema específico do PSPACE (de preferência natural) com complexidade de tempo ?

O (2^{n})

$O(2^n)$

Mohammad Al-Turkistany

O TQBF faria o truque - input: fórmula booleana f, output: existe x1 de tal forma que para todo x2 existe x3 que para todo x4 existe ... existe xn de modo que f (x1 .... xn).

Noam