9
$\begingroup$

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.

$\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$ Nov 2, 2010 at 15:48
  • $\begingroup$ Karp reduction is an approximation preserving reduction. $\endgroup$ Nov 2, 2010 at 17:08
  • 7
    $\begingroup$ I don't understand - why is Karp reduction approximation-preserving? $\endgroup$ 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$ Nov 2, 2010 at 19:14
  • 1
    $\begingroup$ @Oleksandr, Have a look at this (cs.tau.ac.il/~safra/Complexity/PCP.pdf) $\endgroup$ Nov 2, 2010 at 20:08

1 Answer 1

20
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ Could you give a specific (preferably natural) PSPACE-hard problem with $O(2^n)$ time complexity? $\endgroup$ 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$
    – Noam
    Nov 2, 2010 at 20:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.