# What do dichotomy theorems feed on?

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?

• Nice question. I think one intuition is that we are restricting the problems to a class which have nice descriptions. – Kaveh Oct 13 '15 at 2:36
• 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... – Joshua Grochow Oct 13 '15 at 4:58
• Dichotomies occur when the language is too coarse to make fine distinctions. – András Salamon Oct 14 '15 at 1:14