Explore BrainMass

Automata and Variables

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

See attached file for full problem description.


Solution Preview

I have attached the solution to this here. The main idea is to make use of the fact we know from the first part cleverly in the second part. That is where the common variable b comes handy. The part showing that the satisfiability of 3-SAT clause implies #-assignment is routine. On the converse part we need to use the trick.

Here is a quick idea to the ...

Solution Summary

Automata are assessed.