# NP Completeness of 3-SAT problem [closed]

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?

-

## closed as unclear what you're asking by D.W.♦, Yuval Filmus, David Richerby, vonbrand, Luke MathiesonMay 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.

For general ideas and approaches, see here and here. – Juho May 6 '14 at 13:12
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 – 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.