I have started reading on algorithmic complexity for my thesis work. Already have studied on Polynomial time reducibility, NP-Complete, NP-Hard. Now trying to prove NP completeness of some of the classical problems. I have started with 3-SAT problem.

3-SAT problem — was shown to be NP-complete:

Input: A boolean Formula F in CNF where each clause contains at most three variables.

Question: Is that formula satisfiable?

Show now that the simple 3-SAT problem is also NP-complete:

Input: A boolean Formula F in CNF where each clause contains at most three variables and only clauses of length two may contain negated variables.

Question: Is that formula satisfiable?

Can any please explain the main idea? Thank you in advance.


closed as unclear what you're asking by D.W., Yuval Filmus, David Richerby, vonbrand, Luke Mathieson May 8 '14 at 0:24

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ For general ideas and approaches, see here and here. $\endgroup$ – Juho May 6 '14 at 13:12
  • $\begingroup$ this is one of the most common/basic/earliest NP complete reductions found in many refs.... eg wikipedia. also there is some connection to the tseitin transform $\endgroup$ – vzn May 6 '14 at 15:12

Main idea: For each variable $x_i$ introduce a new variable $y_i$ and add a new clause $(\lnot x_i, \lnot y_i)$. Replace each occurence of $\lnot x_i$ in the original clauses by $y_i$.

The new clauses ensure that $y_i$ can be set to true if and only if $x_i$ is false. Thus we neither add nor remove satisfying assignments for the original clauses, while the new clauses can always be satisfied.

  • $\begingroup$ Thank you. Seems I have got some idea. Is there any way to reduce to graph problem? $\endgroup$ – vessilli May 6 '14 at 13:02
  • 2
    $\begingroup$ Any NP-complete problem can be reduced to any other NP-complete problem. The question is just how complex the reduction function will get. $\endgroup$ – FrankW May 6 '14 at 13:05

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