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?

  • 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 '15 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$ – Joshua Grochow Oct 13 '15 at 4:58
  • 1
    $\begingroup$ Dichotomies occur when the language is too coarse to make fine distinctions. $\endgroup$ – András Salamon Oct 14 '15 at 1:14

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).


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.