It is mentioned in a comment in another cstheorySE post 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?

  • 2
    $\begingroup$ See arxiv.org/pdf/math/9409225.pdf $\endgroup$
    – Saeed
    Commented Mar 29, 2014 at 0:41
  • 4
    $\begingroup$ This paper seems to give PTAS results for PSPACE-complete problems: cs.albany.edu/~madhav/pubs.d/stoc94.ps $\endgroup$ Commented Mar 29, 2014 at 2:13
  • 4
    $\begingroup$ 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. $\endgroup$
    – usul
    Commented Mar 29, 2014 at 4:03
  • 1
    $\begingroup$ 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. $\endgroup$
    – Yonatan N
    Commented Mar 30, 2014 at 21:18
  • $\begingroup$ 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? $\endgroup$
    – zxzx179
    Commented Sep 2, 2017 at 3:43

1 Answer 1


As there is no answer yet, I turn my comment to answer, Marathe et al. in their ICALP93 paper, 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.


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.