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
