12
$\begingroup$

It is well known that certain classes of NP-problems have dichotomy theorems, which guarantee that every task in the class is either NP-complete or is in P. The best known such result is Schaefer's dichotomy theorem, along with a number of generalizations.

My understanding is that proving these dichotomy theorems is not really easy. I wonder, if there is any relatively short explanation for why certain classes have dichotomy theorems, while others do not? What is the essential problem structure that makes these theorems possible? Or perhaps there is no such clearly understood structure, rather it is a mystery in each case why the class does or does not have a dichotomy theorem?

$\endgroup$
3
  • 3
    $\begingroup$ Nice question. I think one intuition is that we are restricting the problems to a class which have nice descriptions. $\endgroup$
    – Kaveh
    Oct 13, 2015 at 2:36
  • 6
    $\begingroup$ This isn't an answer, but perhaps points to where an answer might (not) be: if the class of problems is large enough to include all of $\mathsf{NP}$ (or even just a particular subset of it), then Ladner's Theorem will apply and there won't be a dichotomy. So a class with dichotomy at least has to be structured enough to avoid Ladner... $\endgroup$ Oct 13, 2015 at 4:58
  • 1
    $\begingroup$ Dichotomies occur when the language is too coarse to make fine distinctions. $\endgroup$ Oct 14, 2015 at 1:14

1 Answer 1

2
$\begingroup$

For the case of Schaefer's dichotomy theorem, informally, the universal expressive power of Boolean CNF formulas built from non-Schaefer logical relations is behind the dichotomy. Every logical relation is definable by such formula using existential quantifier. This is stated formally in Schaefer's expressibility theorem (Theorem 2.5).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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