<p>Theorem 5.14 of Khanna, Sudan, Trevisan and Williamson [KSTW01] gives a dichotomy theorem for the gap versions with perfect completeness for the boolean MaxCSP problems.</p>

<p>[KSTW01] Sanjeev Khanna, Madhu Sudan, Luca Trevisan and David P. Williamson.  The approximability of constrant satisfaction problems.  <em>SIAM Journal on Computing</em>, 30(6):1863–1920, 2001.  <a href="http://dx.doi.org/10.1137/S0097539799349948">http://dx.doi.org/10.1137/S0097539799349948</a></p>

CC BY-SA 2.5
2010-10-23T13:24:20.580Z
Interesting paper. How is this dichotomy theorem related to Raghavendra's result in Dana's answer?.
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-10-23T13:35:28.160Z
I think that the results are fairly different.  The theorem in [KSTW01] which I mentioned in this answer is about perfect completeness version whereas Raghavendra’s result is not.  The theorem in [KSTW01] is about boolean CSP, whereas Raghavendra’s is about CSP over any domain.  But you should check by yourself, because I do not know the paper by Raghavendra well.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-23T12:54:59.370Z
2010-10-23T12:54:59.370Z
Tsuyoshi Ito
<p>If I'm not mistaken, the definitive result on this front is by Nadia Creignou, who showed that <a href="http://dblp.uni-trier.de/rec/bibtex/journals/jcss/Creignou95" rel="nofollow">every problem in MAX CSP is either polytime solvable, or is MAX SNP-hard</a>. </p>

CC BY-SA 2.5
2010-10-06T08:04:52.307Z
MAX 2-SAT is MAX SNP-hard but very easily solvable for satisfiable instances (2-SAT $\in P$ while 3-SAT is not known to be in $P$). It is $NP$-hard to have $7/8+\epsilon$ -approximation for Max 3-SAT even for satisfiable instances (for any $\epsilon \gt 0$).
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-10-05T23:06:22.353Z
2010-10-05T23:06:22.353Z
Suresh Venkat
<p>Prasad Raghavendra in the STOC'08 best paper proved a dichotomy conjecture for approximating Max-CSP assuming the Unique Games Conjecture. This is not how he presented it originally, but he did give talks presenting things this way a couple of years later, e.g., at the IAS, where it was videotaped:
<a href="http://www.math.ias.edu/seminars/abstract?event=36669">http://www.math.ias.edu/seminars/abstract?event=36669</a></p>

<p>The difference from showing SNP-hardness is that here we talk about quantitatively optimal results.</p>

CC BY-SA 2.5
2010-10-06T02:35:57.000Z
what does 'quantitatively optimal' mean ?
Suresh Venkat
CC BY-SA 2.5
2010-10-06T17:13:43.460Z
hardness factor that matches the best known approximation algorithm
Dana Moshkovitz
CC BY-SA 2.5
2010-10-06T01:03:27.757Z
2010-10-06T01:03:27.757Z
Dana Moshkovitz
<p>An equivalent formulation of PCP theorem is: For Max 3-SAT it is $NP$-hard to distinguish between satisfiable formulas and formulas where at most $r$-fraction of the clauses are satisfiable (for some $r\lt 1$). </p>

<blockquote>
  <p>Is there any known dichotomy theorem that classifies all Max CSP based on whether they have hard gaps or not?</p>
</blockquote>

<p><strong>Edit Dec 16, 2010</strong>: MAX CSP with hard gap means that the problem has optimal inapproximability factor. For instance, 3SAT has hard gap at location one since it is polynomial time approximable to a factor $7/8$ but it is $NP$-hard to obtain approximation factor $7/8+ \epsilon$ even when all clauses are satisfiable.</p>

<cc.complexity-theory><pcp><csp>
Hard gaps in maximum constraint satisfaction problems?
Mohammad Al-Turkistany
# Hard gaps in maximum constraint satisfaction problems?

(Asked by: username_0 on 2010-10-05)

An equivalent formulation of PCP theorem is: For Max 3-SAT it is $NP$-hard to distinguish between satisfiable formulas and formulas where at most $r$-fraction of the clauses are satisfiable (for some $r\lt 1$).

> Is there any known dichotomy theorem that classifies all Max CSP based on whether they have hard gaps or not?

**Edit Dec 16, 2010**: MAX CSP with hard gap means that the problem has optimal inapproximability factor. For instance, 3SAT has hard gap at location one since it is polynomial time approximable to a factor $7/8$ but it is $NP$-hard to obtain approximation factor $7/8+ \epsilon$ even when all clauses are satisfiable.

**Tags:** cc.complexity-theory, pcp, csp


---

## 3 answers

### Answer by username_3 on 2010-10-06. Score: 18 | Accepted answer

Prasad Raghavendra in the STOC'08 best paper proved a dichotomy conjecture for approximating Max-CSP assuming the Unique Games Conjecture. This is not how he presented it originally, but he did give talks presenting things this way a couple of years later, e.g., at the IAS, where it was videotaped:
<http://www.math.ias.edu/seminars/abstract?event=36669>

The difference from showing SNP-hardness is that here we talk about quantitatively optimal results.

> **Comments:**
> **username_2**: what does 'quantitatively optimal' mean ?  
> **username_3**: hardness factor that matches the best known approximation algorithm  

---

### Answer by username_1 on 2010-10-23. Score: 6

Theorem 5.14 of Khanna, Sudan, Trevisan and Williamson [KSTW01] gives a dichotomy theorem for the gap versions with perfect completeness for the boolean MaxCSP problems.

[KSTW01] Sanjeev Khanna, Madhu Sudan, Luca Trevisan and David P. Williamson. The approximability of constrant satisfaction problems. *SIAM Journal on Computing*, 30(6):1863–1920, 2001. <http://dx.doi.org/10.1137/S0097539799349948>

> **Comments:**
> **username_0**: Interesting paper. How is this dichotomy theorem related to Raghavendra's result in Dana's answer?.  
> **username_1**: I think that the results are fairly different.  The theorem in [KSTW01] which I mentioned in this answer is about perfect completeness version whereas Raghavendra’s result is not.  The theorem in [KSTW01] is about boolean CSP, whereas Raghavendra’s is about CSP over any domain.  But you should check by yourself, because I do not know the paper by Raghavendra well.  

---

### Answer by username_2 on 2010-10-05. Score: 4

If I'm not mistaken, the definitive result on this front is by Nadia Creignou, who showed that [every problem in MAX CSP is either polytime solvable, or is MAX SNP-hard](http://dblp.uni-trier.de/rec/bibtex/journals/jcss/Creignou95).

> **Comments:**
> **username_0**: MAX 2-SAT is MAX SNP-hard but very easily solvable for satisfiable instances (2-SAT $\in P$ while 3-SAT is not known to be in $P$). It is $NP$-hard to have $7/8+\epsilon$ -approximation for Max 3-SAT even for satisfiable instances (for any $\epsilon \gt 0$).  

---

