<p>While there are numerous individual examples of sharp thresholds (2-coloring vs 3-coloring is another one), probably the best <em>structural</em> result along the lines you're looking for is <a href="http://en.wikipedia.org/wiki/Schaefer%27s_dichotomy_theorem">Schaefer's dichotomy theorem</a>. </p>

<p>Roughly speaking, the theorem looks at very general classes of problems (called constraint satisfaction problems) and completely characterizes (merely in terms of the kind of input) when the problem is NP-complete and when it's in P. </p>

<p>I haven't read it, but the linked wikipedia page indicates a recent survey by Hubie Chen that presents this result in a more general framework. </p>

CC BY-SA 3.0
2012-09-21T21:18:35.983Z
"The Complexity of Satisfiability Problems: Refining Schaefer’s Theorem" by Allender et al. gives an improved taxonomy of Boolean CSPs.
Huck Bennett
CC BY-SA 3.0
2012-09-21T19:12:07.493Z
2012-09-21T19:12:07.493Z
Suresh Venkat
<p>The <a href="http://en.wikipedia.org/wiki/Boolean_satisfiability_problem">boolean satisfiability problem</a> is in $\mathcal{NPC}$. But if you only get <a href="http://en.wikipedia.org/wiki/Horn-satisfiability">Horn clauses</a>, it is in $\mathcal{P}$.</p>

<p>I've already heard similar statements. Do you know a more general statement when problems in $\mathcal{NPC}$ get to problems in $\mathcal{P}$ because of restrictions? </p>

<p>If something like that does not exist, do you know literature where such restrictions are described?</p>

CC BY-SA 3.0
2012-09-22T19:08:44.057Z
somewhat related, [how subtle problem formulation affects complexity](http://cs.stackexchange.com/questions/4667/complexity-of-decision-problems-vs-computing-functions); gave two other examples there, PCP and "fullness of Regexps."
vzn
CC BY-SA 3.0
2012-09-22T19:11:51.463Z
see also cs.se, [dealing with intractability of NP complete problems](http://cs.stackexchange.com/questions/1477/dealing-with-intractability-np-complete-problems)
vzn
<cc.complexity-theory><reference-request><complexity-classes><np>
Literature for restrictions that make NPC-Problems to P
Martin Thoma
# Literature for restrictions that make NPC-Problems to P

(Asked by: username_0 on 2012-09-21)

The [boolean satisfiability problem](http://en.wikipedia.org/wiki/Boolean_satisfiability_problem) is in $\mathcal{NPC}$. But if you only get [Horn clauses](http://en.wikipedia.org/wiki/Horn-satisfiability), it is in $\mathcal{P}$.

I've already heard similar statements. Do you know a more general statement when problems in $\mathcal{NPC}$ get to problems in $\mathcal{P}$ because of restrictions?

If something like that does not exist, do you know literature where such restrictions are described?

**Tags:** cc.complexity-theory, reference-request, complexity-classes, np
> **Comments:**
> **username_1**: somewhat related, [how subtle problem formulation affects complexity](http://cs.stackexchange.com/questions/4667/complexity-of-decision-problems-vs-computing-functions); gave two other examples there, PCP and "fullness of Regexps."  
> **username_1**: see also cs.se, [dealing with intractability of NP complete problems](http://cs.stackexchange.com/questions/1477/dealing-with-intractability-np-complete-problems)  

---

## 1 answers

### Answer by username_2 on 2012-09-21. Score: 8

While there are numerous individual examples of sharp thresholds (2-coloring vs 3-coloring is another one), probably the best *structural* result along the lines you're looking for is [Schaefer's dichotomy theorem](http://en.wikipedia.org/wiki/Schaefer%27s_dichotomy_theorem).

Roughly speaking, the theorem looks at very general classes of problems (called constraint satisfaction problems) and completely characterizes (merely in terms of the kind of input) when the problem is NP-complete and when it's in P.

I haven't read it, but the linked wikipedia page indicates a recent survey by Hubie Chen that presents this result in a more general framework.

> **Comments:**
> **username_3**: "The Complexity of Satisfiability Problems: Refining Schaefer’s Theorem" by Allender et al. gives an improved taxonomy of Boolean CSPs.  

---

