Automata and Variables
Not what you're looking for?
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.
Purchase this Solution
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 ...
Purchase this Solution
Free BrainMass Quizzes
Word 2010: Table of Contents
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.