Émission de compréhension de la réduction du SAT à 3-SAT en temps poly

Question

Lisant cela http://classes.soe.ucsc.edu/cmps102/spring10/lect/17/sat-3sat-and-other-red.pdf, J'ai appris que la réduction d'une clause $ c_i $ d'une instance $ sat $ contenant plus de 3 littéraux à une instance de 3 $ à 3 $ est fait de cette façon,

Supposons que $ c_1 $ soit $ {x_1, x_2, x_3, x_4 } $. Sa représentation équivalente dans les clauses de 3 lits est,

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

Le problème réside ici. Supposons que pour $ c_1 $, tous les littéraux sont $ false $ sauf pour $ x_2 $. Pour $ c_ {3-sat} $, la première clause serait en effet $ vrai $, mais la valeur booléenne de la deuxième clause dépend du choix de $ y_1 $. Et si nous choisissons $ y_1 = true $? Ensuite, $ c_ {3-sat} $ sera $ false $, mais $ c_1 $ est $ vrai $, réalisant une fausse réduction.