2
$\begingroup$

In http://web.mit.edu/neboat/www/6.046-fa09/rec8.pdf, I see that they pad a 2SAT clause $(x\vee y)$ to make it a 3SAT clause by writing $(x\vee y\vee p) \wedge (x\vee y\vee \neg p)$. Why doesn't $(x\vee y\vee y)$ work instead? Isn't the truth table identical?

$\endgroup$
3
$\begingroup$

Sometimes we insist that the three literals in a 3SAT clause belong to different variables. This ensures, for example, that a random assignment satisfies a clause with probability exactly $7/8$. The translation $x \lor y \lor y$ doesn't satisfy this condition, but the other one does.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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