Question

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.

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top