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

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Could you give a specific (preferably natural) PSPACE-hard problem with $O(2^n)$ time complexity? $\endgroup$ – Mohammad Al-Turkistany Nov 2 '10 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 '10 at 20:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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