15
$\begingroup$

A problem P is said to be in APX if there exists some constant c > 0 such that a polynomial-time approximation algorithm exists for P with approximation factor 1 + c.

APX contains PTAS (seen by simply picking any constant c > 0) and P.

Is APX in NP? In particular, does the existence of a polynomial-time approximation algorithm for some approximation factor imply that the problem is in NP?

$\endgroup$
  • $\begingroup$ I think "what is known about class X relative to all other classes Y" is far too vague as a question, unless some further details are provided about the kinds of relationships sought. $\endgroup$ – András Salamon Aug 19 '10 at 1:25
  • $\begingroup$ I mean relationships such as 'contains', 'is contained in', 'does not contain'. $\endgroup$ – Andrew W. Aug 19 '10 at 2:19
  • $\begingroup$ After some thinking, I've narrowed the question down to the specific relationship I am most interested in. $\endgroup$ – Andrew W. Aug 19 '10 at 3:13
  • 1
    $\begingroup$ What exactly does it mean to ask if APX is contained in NP? APX consists of approximable "NP-optimization" problems whereas NP consists of decision problems. Furthermore, by definition, the decision version of an NP-optimization problem is in NP. Maybe you had something else in mind? $\endgroup$ – Joshua Grochow Aug 19 '10 at 4:19
  • $\begingroup$ You are right Joshua. Ian answered the question I should have asked. $\endgroup$ – Andrew W. Aug 19 '10 at 12:38
20
$\begingroup$

APX is defined as a subset of NPO, so yes, if an optimization problem is in APX then the corresponding decision problem is in NP.

However, if what you're asking is whether an arbitrary problem must be in NP (or NPO) if there is a poly time O(1)-approximation, then the answer is no. I don't know of any natural problems that serve as a counter-example, but one could define an artificial maximization problem where the objective is the sum of two terms, a large term that is easily optimized in P, and a much smaller term that adds a small amount if part of the solution encodes an answer to some hard problem (outside of NP). Then you could find, say, a 2-approximation in poly time by concentrating on the easy term, but finding an optimal solution would require solving the hard problem.

$\endgroup$
  • 2
    $\begingroup$ I accepted your answer because it addressed both the question I asked ('Is APX contained in NP?') and the question I should have asked ('Does a poly-time O(1) approx imply exact solution in NP?'). $\endgroup$ – Andrew W. Aug 19 '10 at 12:38
  • 1
    $\begingroup$ A broad of class of problems which are not contained in NPO and NP but have constant-factor approximation is the class of online problems (The question on what complexity class contains online problems is here cstheory.stackexchange.com/questions/1664/…). $\endgroup$ – Oleksandr Bondarenko Oct 3 '10 at 17:08
8
$\begingroup$

APX is discussed and (like other complexity classes) updated regularly in the Complexity Zoo.

http://qwiki.stanford.edu/wiki/Complexity_Zoo:A#apx

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.