# Hard gaps in maximum constraint satisfaction problems?

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.

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.

• what does 'quantitatively optimal' mean ? Oct 6, 2010 at 2:35
• hardness factor that matches the best known approximation algorithm Oct 6, 2010 at 17:13

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

• Interesting paper. How is this dichotomy theorem related to Raghavendra's result in Dana's answer?. Oct 23, 2010 at 13:24
• 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. Oct 23, 2010 at 13:35

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.

• 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$). Oct 6, 2010 at 8:04