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?

Improve this question
$\endgroup$
2

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
1
  • 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
    Commented Sep 21, 2012 at 21:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.