11
$\begingroup$

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.

|cite|improve this question
$\endgroup$
17
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • 3
    $\begingroup$ what does 'quantitatively optimal' mean ? $\endgroup$ – Suresh Venkat Oct 6 '10 at 2:35
  • 3
    $\begingroup$ hardness factor that matches the best known approximation algorithm $\endgroup$ – Dana Moshkovitz Oct 6 '10 at 17:13
6
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Interesting paper. How is this dichotomy theorem related to Raghavendra's result in Dana's answer?. $\endgroup$ – Mohammad Al-Turkistany Oct 23 '10 at 13:24
  • $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Oct 23 '10 at 13:35
4
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ 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$). $\endgroup$ – Mohammad Al-Turkistany Oct 6 '10 at 8:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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