Purchase Solution

# Automata and Variables

Not what you're looking for?

Let &#61542; be a 3cnf-formula. An &#61625; assignment to the variables of &#61542; is one where each clause contains two literals with unequal truth values. In other words an &#61625; -assignment satisfies &#61542; without assigning three true literals in any clause.

a. Show that the negation of any &#61625;-assignment to &#61542; is also an &#61625;-assignment.
b. Let &#61625;SAT be the collection of 3cnf-formulas that have an &#61625;-assignment. Show that we obtain a polynomial time reduction from 3SAT to &#61625;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 &#61625;SAT is NP-complete

See attached file for full problem description.

##### Solution Summary

Automata are assessed.

##### 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 ...

##### Free BrainMass Quizzes

Ever wondered where a Table of Contents in a Word document comes from? Maybe you need a refresher on the topic? This quiz will remind you of the keywords and options used when working with a T.O.C. in Word 2010.

##### C# variables and classes

This quiz contains questions about C# classes and variables.

##### Basic Networking Questions

This quiz consists of some basic networking questions.

##### Basic Computer Terms

We use many basic terms like bit, pixel in our usual conversations about computers. Are we aware of what these mean? This little quiz is an attempt towards discovering that.

##### Excel Introductory Quiz

This quiz tests your knowledge of basics of MS-Excel.