Existe-t-il un problème complet PSPACE complet qui a un algorithme FPTAS?

9

Il est bien connu que le problème NP-Complete appelé Subset Sum a un FPTAS. Je me demandais s'il existait un problème PSPACE Complete qui a également un FPTAS? Merci d'avance.

ds.algorithms space-bounded big-picture Zelah 02
la source
5
Je suppose que la réponse serait non. La partition 3 n'admet pas FPTAS car elle est fortement NP-complète à moins que P = NP. En outre, il y a une réduction de Karp de 3 partitions à tout problème de concurrence avec PSPACE. Par conséquent, FPTAS pour tout problème PSPACE complet impliquerait FPTAS pour 3 partitions, ce qui est impossible à moins que P = NP.
Mohammad Al-Turkistany
La réduction de Karp est une réduction préservant l'approximation.
Mohammad Al-Turkistany
7
Je ne comprends pas - pourquoi la réduction de Karp préserve-t-elle l'approximation?
Peter Shor
3
La réduction de Karp est définie pour les problèmes de décision, toute réduction préservant l'approximation est définie pour les problèmes d'optimisation. Par conséquent, la réduction de Karp ne peut pas être une réduction préservant l'approximation.
Oleksandr Bondarenko
1
@Oleksandr, Jetez un œil à cela ( cs.tau.ac.il/~safra/Complexity/PCP.pdf )
Mohammad Al-Turkistany

Réponses:

20

f(x)=2|x|+g(x)g(x)2nfϵ>2−|x|2|x|f

Noam
la source
1
O(2n)
5
TQBF ferait l'affaire - entrée: formule booléenne f, sortie: existe-t-il x1 tel que pour tout x2 il existe x3 que pour tout x4 existe ... existe xn tel que f (x1 .... xn).
Noam