Explore BrainMass
Share

Explore BrainMass

    Automata and Variables

    This content was COPIED 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 9, 2019, 7:31 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