<p>See the following paper by Khanna etal on syntactic vs computational views of approximability. MaxSNP is a syntactic class while APX is a computational class. dl.acm.org/citation.cfm?id=298507</p>

<p>Made comment into answer as per Suresh's request.</p>

CC BY-SA 3.0
2015-04-25T17:38:24.970Z
2015-04-25T17:38:24.970Z
Chandra Chekuri
<p>$MaxSNP=APX$. This is according to <a href="http://en.m.wikipedia.org/wiki/APX" rel="nofollow">Wikipedia</a></p>

CC BY-SA 3.0
2015-01-24T13:04:55.543Z
That is interesting. In the Wikipedia article about $MaxSNP$ it says: "The closure of MaxSNP under PTAS reductions is APX."
R B
CC BY-SA 3.0
2015-01-24T11:15:21.560Z
2015-01-24T12:25:59.597Z
2015-01-24T12:25:59.597Z
Mohammad Al-Turkistany
<p>My understanding of these classes is a really fuzzy. The more I am trying to read the more I am getting confused. Can anyone help me understand the relationship between these classes. More precisely, is $\mathsf{MaxSNP} = \mathsf{APX}$  or $\mathsf{MaxSNP} \subset\mathsf{APX}$? </p>

<p>Thanks a lot in advance. :)</p>

CC BY-SA 3.0
2015-01-23T14:21:09.707Z
See the following paper by Khanna etal on syntactic vs computational views of approximability. MaxSNP is a syntactic class while APX is a computational class. http://dl.acm.org/citation.cfm?id=298507
Chandra Chekuri
CC BY-SA 3.0
2015-02-03T14:58:49.307Z
Thanks a lot for your reply. I really appreciate your effort.
user1105
CC BY-SA 3.0
2015-04-25T05:51:59.210Z
@ChandraChekuri comment -> answer ?
Suresh Venkat
<cc.complexity-theory><approximation-hardness>
What is the relationship between $\mathsf{APX}$ and $\mathsf{MaxSNP}$ classes?
user1105
# What is the relationship between $\mathsf{APX}$ and $\mathsf{MaxSNP}$ classes?

(Asked by: username_0 on 2015-01-23)

My understanding of these classes is a really fuzzy. The more I am trying to read the more I am getting confused. Can anyone help me understand the relationship between these classes. More precisely, is $\mathsf{MaxSNP} = \mathsf{APX}$ or $\mathsf{MaxSNP} \subset\mathsf{APX}$?

Thanks a lot in advance. :)

**Tags:** cc.complexity-theory, approximation-hardness

> **Comments:**
> **username_1**: See the following paper by Khanna etal on syntactic vs computational views of approximability. MaxSNP is a syntactic class while APX is a computational class. http://dl.acm.org/citation.cfm?id=298507  
> **username_0**: Thanks a lot for your reply. I really appreciate your effort.  
> **username_2**: @ChandraChekuri comment -> answer ?  

---

## 2 answers

### Answer by username_1 on 2015-04-25. Score: 2 | Accepted answer

See the following paper by Khanna etal on syntactic vs computational views of approximability. MaxSNP is a syntactic class while APX is a computational class. dl.acm.org/citation.cfm?id=298507

Made comment into answer as per Suresh's request.


---

### Answer by username_3 on 2015-01-24. Score: 0

$MaxSNP=APX$. This is according to [Wikipedia](http://en.m.wikipedia.org/wiki/APX)

> **Comments:**
> **username_4**: That is interesting. In the Wikipedia article about $MaxSNP$ it says: "The closure of MaxSNP under PTAS reductions is APX."  

---

