<p>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 <a href="http://www.sciencedirect.com/science/article/pii/S0890540103000373" rel="nofollow">Schaefer's expressibility theorem</a> (Theorem 2.5).</p>

CC BY-SA 3.0
2015-10-13T07:57:17.653Z
2015-10-13T12:23:18.753Z
2015-10-13T12:23:18.753Z
Mohammad Al-Turkistany
<p>It is well known that certain classes of <strong>NP</strong>-problems have <em>dichotomy theorems,</em> which guarantee that every task in the class is either <strong>NP</strong>-complete or is in <strong>P</strong>. The best known such result is 
<a href="https://en.wikipedia.org/wiki/Schaefer%27s_dichotomy_theorem">Schaefer's dichotomy 
theorem</a>, along with a number of generalizations.</p>

<p>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?</p>

CC BY-SA 3.0
2015-10-13T02:36:12.573Z
Nice question. I think one intuition is that we are restricting the problems to a class which have nice descriptions.
Kaveh
CC BY-SA 3.0
2015-10-13T04:58:38.610Z
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
CC BY-SA 3.0
2015-10-14T01:14:03.493Z
Dichotomies occur when the language is too coarse to make fine distinctions.
András Salamon
<cc.complexity-theory><np><descriptive-complexity>
What do dichotomy theorems feed on?
Andras Farago
# What do dichotomy theorems feed on?

(Asked by: username_0 on 2015-10-13)

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](https://en.wikipedia.org/wiki/Schaefer%27s_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?

**Tags:** cc.complexity-theory, np, descriptive-complexity
> **Comments:**
> **username_1**: Nice question. I think one intuition is that we are restricting the problems to a class which have nice descriptions.  
> **username_2**: 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...  
> **username_3**: Dichotomies occur when the language is too coarse to make fine distinctions.  

---

## 1 answers

### Answer by username_4 on 2015-10-13. Score: 2

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](http://www.sciencedirect.com/science/article/pii/S0890540103000373) (Theorem 2.5).


---

