# Does PSPACE-completeness imply approximation hardness?

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?

• – Saeed Mar 29 '14 at 0:41
• This paper seems to give PTAS results for PSPACE-complete problems: cs.albany.edu/~madhav/pubs.d/stoc94.ps – Sasho Nikolov Mar 29 '14 at 2:13
• 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 Mar 29 '14 at 4:03
• 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 Mar 30 '14 at 21:18
• 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? – Stupid_Guy Sep 2 '17 at 3:43