15

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?

Community
  • 1
R B
  • 9,448
  • 5
  • 34
  • 74
  • 2
    See http://arxiv.org/pdf/math/9409225.pdf – Saeed Mar 29 '14 at 00:41
  • 4
    This paper seems to give PTAS results for PSPACE-complete problems: http://www.cs.albany.edu/~madhav/pubs.d/stoc94.ps – Sasho Nikolov Mar 29 '14 at 02:13
  • 4
    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 04:03
  • 1
    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? – zxzx179 Sep 02 '17 at 03:43

1 Answers1

3

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.

Saeed
  • 3,440
  • 1
  • 22
  • 39