<p>As there is no answer yet, I turn my comment to answer, Marathe et al. in their <a href="http://arxiv.org/pdf/math/9409225.pdf" rel="nofollow">ICALP93 paper</a>, defined some problems which are PSPACE complete but they admit constant factor approximations, they also provide some inapproximability results. For this particular question, consider MAX3SAT, corresponding decision problem is PSPACE-complete even if the corresponding SAT graph has hierarchical structure as they defined in their paper, but this problem has a 2-approximation guarantee algorithm in hierarchical structure.</p>

CC BY-SA 3.0
2014-04-01T11:35:03.770Z
2014-04-01T11:35:03.770Z
Saeed
<p>It is mentioned in a comment in another <a href="https://cstheory.stackexchange.com/questions/19133/a-reachability-problem#comment49492_19133">cstheorySE post</a> that PSPACE-completeness imply APX-hardness. Can anyone please explain/share a reference for it?</p>

<p>Is this "tight"? (i.e., are there PSPACE-complete problems whose optimization problem admits constant factor approximation in poly time?)</p>

<p>What about completeness for some level of PH? Does it imply any approximation hardness?</p>

CC BY-SA 3.0
2014-03-29T00:41:15.320Z
See http://arxiv.org/pdf/math/9409225.pdf
Saeed
CC BY-SA 3.0
2014-03-29T02:13:03.923Z
This paper seems to give PTAS results for PSPACE-complete problems: http://www.cs.albany.edu/~madhav/pubs.d/stoc94.ps
Sasho Nikolov
CC BY-SA 3.0
2014-03-29T04:03:38.187Z
Ugh, that was a bad comment. The idea was to make a heuristic guess, so sorry if it came across as a statement of fact! One is a class of decision problems and one is a class of function problems, so the statement isn't even well-defined. I think the reasoning was just that you can answer a problem in APX exactly using polynomial space. But it would take some work to formalize the connection and I wasn't referring to any formal results that I knew of.
usul
CC BY-SA 3.0
2014-03-30T21:18:02.853Z
The two ideas seem rather distinct. Presumably, the objective function $f(x)$ for most problems can be modified to $\hat{f}(x) = f(x) + nk$ where $k$ is an upper bound on the values $f$ can take on feasible solutions. $\hat{f}$ is then still just as hard to compute exactly as is $f$, but it trivially has a $(1-\epsilon)$ (or even $(1-1/n)$) approximation algorithm when there's a feasible solution. This argument should hold for classes even "harder" than PSPACE-complete.
Yonatan N
CC BY-SA 3.0
2017-09-02T03:43:54.273Z
If I remembered it correctly, APX are just defined for NP optimization problems?
 i.e., APX $\subseteq $ NP-optimization. When we talk about PSPACE-Complete, aren't we already beyond the regime of the definition?
zxzx179
<cc.complexity-theory><approximation-algorithms><approximation-hardness><np><pspace>
Does PSPACE-completeness imply approximation hardness?
R B
# Does PSPACE-completeness imply approximation hardness?

(Asked by: username_0 on 2014-03-29)

It is mentioned in a comment in another [cstheorySE post](https://cstheory.stackexchange.com/questions/19133/a-reachability-problem#comment49492_19133) that PSPACE-completeness imply APX-hardness. Can anyone please explain/share a reference for it?

Is this "tight"? (i.e., are there PSPACE-complete problems whose optimization problem admits constant factor approximation in poly time?)

What about completeness for some level of PH? Does it imply any approximation hardness?

**Tags:** cc.complexity-theory, approximation-algorithms, approximation-hardness, np, pspace

> **Comments:**
> **username_1**: See http://arxiv.org/pdf/math/9409225.pdf  
> **username_2**: This paper seems to give PTAS results for PSPACE-complete problems: http://www.cs.albany.edu/~madhav/pubs.d/stoc94.ps  
> **username_3**: Ugh, that was a bad comment. The idea was to make a heuristic guess, so sorry if it came across as a statement of fact! One is a class of decision problems and one is a class of function problems, so the statement isn't even well-defined. I think the reasoning was just that you can answer a problem in APX exactly using polynomial space. But it would take some work to formalize the connection and I wasn't referring to any formal results that I knew of.  
> **username_4**: The two ideas seem rather distinct. Presumably, the objective function $f(x)$ for most problems can be modified to $\hat{f}(x) = f(x) + nk$ where $k$ is an upper bound on the values $f$ can take on feasible solutions. $\hat{f}$ is then still just as hard to compute exactly as is $f$, but it trivially has a $(1-\epsilon)$ (or even $(1-1/n)$) approximation algorithm when there's a feasible solution. This argument should hold for classes even "harder" than PSPACE-complete.  
> **username_5**: If I remembered it correctly, APX are just defined for NP optimization problems?  i.e., APX $\subseteq $ NP-optimization. When we talk about PSPACE-Complete, aren't we already beyond the regime of the definition?  

---

## 1 answers

### Answer by username_1 on 2014-04-01. Score: 3 | Accepted answer

As there is no answer yet, I turn my comment to answer, Marathe et al. in their [ICALP93 paper](http://arxiv.org/pdf/math/9409225.pdf), defined some problems which are PSPACE complete but they admit constant factor approximations, they also provide some inapproximability results. For this particular question, consider MAX3SAT, corresponding decision problem is PSPACE-complete even if the corresponding SAT graph has hierarchical structure as they defined in their paper, but this problem has a 2-approximation guarantee algorithm in hierarchical structure.


---

