<p>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.</p>

CC BY-SA 2.5
2010-11-02T19:28:55.303Z
Could you give a specific (preferably natural) PSPACE-hard problem with $O(2^n)$ time complexity?
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-11-02T20:06:53.093Z
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).
Noam
CC BY-SA 2.5
2010-11-02T19:04:43.733Z
2010-11-02T19:10:49.757Z
2010-11-02T19:10:49.757Z
Noam
<p>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.</p>

CC BY-SA 2.5
2010-11-02T15:48:45.220Z
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
CC BY-SA 2.5
2010-11-02T17:08:42.733Z
Karp reduction is an approximation preserving reduction.
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-11-02T17:55:26.567Z
I don't understand - why is Karp reduction approximation-preserving?
Peter Shor 
CC BY-SA 2.5
2010-11-02T18:21:03.423Z
Karp reduction between gap problems preserves approximation results.
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-11-02T19:14:46.927Z
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
CC BY-SA 2.5
2010-11-02T20:08:49.717Z
@Oleksandr, Have a look at this (http://www.cs.tau.ac.il/~safra/Complexity/PCP.pdf)
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-11-02T20:32:36.457Z
@turkistany Thank you for the reference. Now your words make sense for me.
Oleksandr Bondarenko
<ds.algorithms><space-bounded><big-picture>
Does There exist a particular PSPACE Complete Problem which has a FPTAS algorithm?
Zelah 02
# Does There exist a particular PSPACE Complete Problem which has a FPTAS algorithm?

(Asked by: username_0 on 2010-11-02)

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.

**Tags:** ds.algorithms, space-bounded, big-picture

> **Comments:**
> **username_1**: 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.  
> **username_1**: Karp reduction is an approximation preserving reduction.  
> **username_2**: I don't understand - why is Karp reduction approximation-preserving?  
> **username_1**: Karp reduction between gap problems preserves approximation results.  
> **username_3**: 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.  
> **username_1**: @Oleksandr, Have a look at this (http://www.cs.tau.ac.il/~safra/Complexity/PCP.pdf)  
> **username_3**: @turkistany Thank you for the reference. Now your words make sense for me.  

---

## 1 answers

### Answer by username_4 on 2010-11-02. Score: 20 | Accepted answer

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.

> **Comments:**
> **username_1**: Could you give a specific (preferably natural) PSPACE-hard problem with $O(2^n)$ time complexity?  
> **username_4**: 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).  

---

