-3
$\begingroup$

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?

$\endgroup$
  • 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
1
$\begingroup$

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.)

$\endgroup$

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