Let be a 3cnf-formula. An assignment to the variables of is one where each clause contains two literals with unequal truth values. In other words an -assignment satisfies without assigning three true literals in any clause.
a. Show that the negation of any -assignment to is also an -assignment.
b. Let SAT be the collection of 3cnf-formulas that have an -assignment. Show that we obtain a polynomial time reduction from 3SAT to SAT by replacing each clause cI
(y1 V y2 V y3)
by the two clauses
(y1 V y2 V zI) and ( V y3 V b)
where zI is a new variable for each clause cI and b is a single additional new variable.
c. Conclude that SAT is NP-complete