16
$\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?

Improve this question
$\endgroup$
5
  • $\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, 2010 at 1:25
  • $\begingroup$ I mean relationships such as 'contains', 'is contained in', 'does not contain'. $\endgroup$
    – Andrew W.
    Aug 19, 2010 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, 2010 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, 2010 at 4:19
  • $\begingroup$ You are right Joshua. Ian answered the question I should have asked. $\endgroup$
    – Andrew W.
    Aug 19, 2010 at 12:38

2 Answers 2

Reset to default
22
$\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.

Improve this answer
$\endgroup$
2
  • 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, 2010 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, 2010 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

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ See also qwiki.stanford.edu/wiki/Complexity_Zoo:G#glo which doesn't seem to be mentioned in the APX entry. $\endgroup$
    – Jukka Suomela
    Aug 18, 2010 at 22:51
  • $\begingroup$ The syntactic characterization of APX (mentioned in the Zoo entry) is particularly beautiful. $\endgroup$
    – Suresh Venkat
    Aug 18, 2010 at 23:28
  • $\begingroup$ The link has expired it seems. $\endgroup$
    – Inuyasha Yagami
    May 26, 2021 at 4:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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