7
$\begingroup$

The boolean satisfiability problem is in $\mathcal{NPC}$. But if you only get Horn clauses, 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?

$\endgroup$
8
$\begingroup$

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.

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.

$\endgroup$
  • 4
    $\begingroup$ "The Complexity of Satisfiability Problems: Refining Schaefer’s Theorem" by Allender et al. gives an improved taxonomy of Boolean CSPs. $\endgroup$ – Huck Bennett Sep 21 '12 at 21:18

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.