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?
$\begingroup$
$\endgroup$
2
-
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$– JuhoMar 25, 2015 at 15:24
-
$\begingroup$ what did u do so far? $\endgroup$– M a m a DMar 25, 2015 at 21:22
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.)
