Discuss teh below:
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