Explore BrainMass
Share

Automata and Variables

This content was STOLEN from BrainMass.com - View the original, and get the already-completed solution here!

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.

© BrainMass Inc. brainmass.com October 24, 2018, 9:14 pm ad1c9bdddf
https://brainmass.com/computer-science/theoretical-computer-science/automata-variables-120805

Attachments

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.

$2.19
See Also This Related BrainMass Solution

Automata and Computability

A Boolean formula is a Boolean circuit wherein every gate has only one output wire. The same input variable may appear in multiple places of a Boolean formula. Prove that a language has a polynomial size family of formulas if it is in NC1. Ignore uniformity considerations.

See attached file for full problem description.

View Full Posting Details