4
$\begingroup$

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.

$\endgroup$

1 Answer 1

8
$\begingroup$

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.)

$\endgroup$
1
  • $\begingroup$ A thousand thanks for your elegant answer! This also helped understand reduction better :) $\endgroup$ Commented Feb 26, 2014 at 14:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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