Let be a 3cnf-formula. An -assignment to the variables of is one where each clause contains two literals with unequal truth values. In

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 c_i

(y₁ ∨ y₂ ∧ y₃)

with the two clauses

(y₁ ∨ y₂ ∨ z_i) and (z̅_i ∨ y₃ ∨ 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.