# Does There exist a particular PSPACE Complete Problem which has a FPTAS algorithm?

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.

• 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. – Mohammad Al-Turkistany Nov 2 '10 at 15:48
• Karp reduction is an approximation preserving reduction. – Mohammad Al-Turkistany Nov 2 '10 at 17:08
• I don't understand - why is Karp reduction approximation-preserving? – Peter Shor Nov 2 '10 at 17:55
• 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. – Oleksandr Bondarenko Nov 2 '10 at 19:14
• @Oleksandr, Have a look at this (cs.tau.ac.il/~safra/Complexity/PCP.pdf) – Mohammad Al-Turkistany Nov 2 '10 at 20:08

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.
• Could you give a specific (preferably natural) PSPACE-hard problem with $O(2^n)$ time complexity? – Mohammad Al-Turkistany Nov 2 '10 at 19:28