I have the following problem: How to show that the special case of SAT, in which each clause has either exactly two literals or at most one negative literal, is NP-complete?

  • 4
    $\begingroup$ Kneejerk answer: you do so by picking a suitable hard problem and constructing a reduction. Assuming you know this, what did you try? Did you get stuck somewhere? $\endgroup$ – Juho Mar 25 '15 at 15:24
  • $\begingroup$ what did u do so far? $\endgroup$ – M a m a D Mar 25 '15 at 21:22

You pick a problem that is NP-complete and show a reduction that shows your problem is at least as hard as that NP-complete problem. As this is a natural exercise problem, you should practice trying it yourself -- we wouldn't be helping anyone to just spoonfeed you the solution.

Alternatively, you use Schaefer's dichotomy theorem. (Comment: If you're just learning the subject, don't expect this to be easier than doing the reduction! This is only if you want to go deeper on the subject.)


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