It is well known that the NP-Complete Problem called Subset Sum has a FPTAS. I was wondering if there existed an PSPACE Complete problem which also has a FPTAS? Thanks in advance.
$\begingroup$
$\endgroup$
7
-
5$\begingroup$ I guess the answer would be no. 3-partition does not admit FPTAS since it is strongly NP-complete unless P=NP. Also, there is a Karp reduction from 3-partition to any PSPACE-compete problem. Therefore, FPTAS for any PSPACE-complete problem would imply FPTAS for 3-partition which is impossible unless P=NP. $\endgroup$– Mohammad Al-TurkistanyCommented Nov 2, 2010 at 15:48
-
$\begingroup$ Karp reduction is an approximation preserving reduction. $\endgroup$– Mohammad Al-TurkistanyCommented Nov 2, 2010 at 17:08
-
7$\begingroup$ I don't understand - why is Karp reduction approximation-preserving? $\endgroup$– Peter ShorCommented Nov 2, 2010 at 17:55
-
3$\begingroup$ Karp reduction is defined for decision problems, any of approximation-preserving reductions is defined for optimization problems. Therefore, Karp reduction can't be an approximation-preserving reduction. $\endgroup$– Oleksandr BondarenkoCommented Nov 2, 2010 at 19:14
-
1$\begingroup$ @Oleksandr, Have a look at this (cs.tau.ac.il/~safra/Complexity/PCP.pdf) $\endgroup$– Mohammad Al-TurkistanyCommented Nov 2, 2010 at 20:08
|
Show 2 more comments
1 Answer
$\begingroup$
$\endgroup$
2
It is possible to define artificial PSPACE-HARD problems with an FPTAS: define $f(x)=2^{|x|}+g(x)$ where $g(x)$ is a Boolean PSPACE-hard problem whose complexity is at most $2^n$, then $f$ is also PSPACE-hard, but it has an FPTAS: if $\epsilon \gt 2^{-|x|}$ then return $2^{|x|}$ else we have enough time to compute $f$ exactly.
-
1$\begingroup$ Could you give a specific (preferably natural) PSPACE-hard problem with $O(2^n)$ time complexity? $\endgroup$ Commented Nov 2, 2010 at 19:28
-
5$\begingroup$ TQBF would do the trick -- input: boolean formula f, output: does there exists x1 such that for all x2 there exists x3 that for all x4 exists ... exists xn such that f(x1....xn). $\endgroup$– NoamCommented Nov 2, 2010 at 20:06