Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Reading this http://classes.soe.ucsc.edu/cmps102/Spring10/lect/17/SAT-3SAT-and-other-red.pdf, I came to know that reducing a clause $C_i$ from a $SAT$ instance containing more than 3 literals to a $3-SAT$ instance is done this way,

Suppose $C_1$ is $\{x_1, x_2, x_3, x_4\}$. It's equivalent representation in 3-literal clauses is,

$C_{3-SAT} = \{\{x_1, x_2, y_1\},\{\bar{y_1}, x_3,x_4\}\}$

The issue lies here. Assume for $C_1$, all the literals are $False$ except for $x_2$. For $C_{3-SAT}$, the first clause would indeed be $True$, but the boolean value for the second clause depends on the choice of $y_1$. What if we chose $y_1 = True$? then, $C_{3-SAT}$ will be $False$, yet $C_1$ is $True$, realizing a false reduction.

share|improve this question
add comment

1 Answer

up vote 6 down vote accepted

The clauses are not intended to be equivalent, so you shouldn't call it an "equivalent representation in 3-literal clauses."

All the reduction requires is that the original formula has at least one satisfying assignment if, and only if, the new formula does. In this case, we have this property: if the original formula was satisfiable, we can choose at least one assignment to the variables $y_i$ that makes the new formula true and it doesn't matter that there are also choices for the $y_i$ that make it false. Conversely, if the original formula was unsatisfiable, no choice of the $y_i$ will make the new formula true.

Formally, there doesn't even have to be any relationship between the values of the variables in the two assignments. In theory, you could map all satisfiable formulas to "$x$" and all unsatisfiable formulas to "$x\wedge \neg x$". (But we don't know of an efficient way to do that.)

share|improve this answer
    
A thousand thanks for your elegant answer! This also helped understand reduction better :) –  Issam Laradji Feb 26 at 14:14
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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