-3
$\begingroup$

This question already has an answer here:

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$

marked as duplicate by Juho, Luke Mathieson, lPlant, Kaveh, Gilles Jun 7 '15 at 16:48

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

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