Problem
Let φ be a 3cnf formula. A non-identical problem, or nid- problem, to the variables of φ is a problem where each clause of φ contains two literals with different truth values, i.e., there cannot be a clause with the 3 true literals. Thus, a nid-problem satisfies φ without assigning true to the 3 literals of any of the clauses.
• Show that the negation of a nid-assignment to φ is also a nid-assignment to φ.
• Let SATnid be the collection of 3cnf formulas that have a nid-assignment. Show that it is possible to obtain a polynomial-time reduction from 3SAT to SATnid by replacing each ci clause of the form (y1 ∨ y2 ∨ y3) by two clauses (y1 ∨ y2 ∨ zi) and (zi ∨ y3 ∨ b) where zi is a new variable for each ci clause, and b is a single additional new variable.
• Conclude that SATnid is NP-complete.
The response must include a reference list. One-inch margins, double-space, Using Times New Roman 12 pnt font and APA style of writing and citations.