[Solved]: NP Completeness of 3-SAT problem

Problem Detail: 

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.

Asked By : vessilli

Answered By : FrankW

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/24450

 Ask a Question

 Download Related Notes/Documents