0
$\begingroup$

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.

$\endgroup$
  • $\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
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\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.