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

<p><a href="http://qwiki.stanford.edu/wiki/Complexity_Zoo:A#apx">http://qwiki.stanford.edu/wiki/Complexity_Zoo:A#apx</a></p>

CC BY-SA 4.0
2021-05-26T04:06:37.680Z
The link has expired it seems.
Inuyasha Yagami
CC BY-SA 2.5
2010-08-18T22:51:01.417Z
See also http://qwiki.stanford.edu/wiki/Complexity_Zoo:G#glo which doesn't seem to be mentioned in the APX entry.
Jukka Suomela
CC BY-SA 2.5
2010-08-18T23:28:24.790Z
The syntactic characterization of APX (mentioned in the Zoo entry) is particularly beautiful.
Suresh Venkat
CC BY-SA 2.5
2010-08-18T22:46:15.527Z
2010-08-18T22:46:15.527Z
Ross Snider
<p>APX is <em>defined</em> as a subset of NPO, so yes, if an optimization problem is in APX then the corresponding decision problem is in NP.</p>

<p>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.</p>

CC BY-SA 2.5
2010-08-19T12:38:04.420Z
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?').
Andrew W.
CC BY-SA 2.5
2010-10-03T17:08:51.973Z
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 http://cstheory.stackexchange.com/questions/1664/is-there-known-any-complexity-class-containing-online-counterparts-of-optimizatio).
Oleksandr Bondarenko
CC BY-SA 2.5
2010-08-19T05:11:52.550Z
2010-08-19T05:11:52.550Z
Ian
<p>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.</p>

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

<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?</p>

CC BY-SA 2.5
2010-08-19T01:25:16.320Z
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.
András Salamon
CC BY-SA 2.5
2010-08-19T02:19:31.010Z
I mean relationships such as 'contains', 'is contained in', 'does not contain'.
Andrew W.
CC BY-SA 2.5
2010-08-19T03:13:50.433Z
After some thinking, I've narrowed the question down to the specific relationship I am most interested in.
Andrew W.
CC BY-SA 2.5
2010-08-19T04:19:51.400Z
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?
Joshua Grochow
CC BY-SA 2.5
2010-08-19T12:38:55.777Z
You are right Joshua. Ian answered the question I should have asked.
Andrew W.
<cc.complexity-theory><complexity-classes><apx>
Is APX contained in NP?
Andrew W.
# Is APX contained in NP?

(Asked by: username_0 on 2010-08-18)

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?

**Tags:** cc.complexity-theory, complexity-classes, apx
> **Comments:**
> **username_1**: 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.  
> **username_0**: I mean relationships such as 'contains', 'is contained in', 'does not contain'.  
> **username_0**: After some thinking, I've narrowed the question down to the specific relationship I am most interested in.  
> **username_2**: 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?  
> **username_0**: You are right Joshua. Ian answered the question I should have asked.  

---

## 2 answers

### Answer by username_7 on 2010-08-19. Score: 22 | Accepted answer

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.

> **Comments:**
> **username_0**: 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?').  
> **username_8**: 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 http://cstheory.stackexchange.com/questions/1664/is-there-known-any-complexity-class-containing-online-counterparts-of-optimizatio).  

---

### Answer by username_3 on 2010-08-18. Score: 8

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

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

> **Comments:**
> **username_5**: See also http://qwiki.stanford.edu/wiki/Complexity_Zoo:G#glo which doesn't seem to be mentioned in the APX entry.  
> **username_6**: The syntactic characterization of APX (mentioned in the Zoo entry) is particularly beautiful.  
> **username_4**: The link has expired it seems.  

---

