MIT OpenCourseWare http ocw mit edu 6 080 6 089 Great Ideas in Theoretical Computer Science Spring 2008 For information about citing these materials or our Terms of Use visit http ocw mit edu terms 6 080 6 089 GITCS Mar 11 2008 Lecture 10 Lecturer Scott Aaronson 1 Scribe Yinmeng Zhang Administrivia Work hard on the homework but don t freak out Come to o ce hours There will be a short 1 week pset before spring break and an exam on the Thursday after which is April 3rd 2 Recap Last time we saw a rough geography of the universe of computational problems NP hard NP complete NP P One of the precepts of this course is that this picture is really important In an ideal world people would recognize this map the same way they recognize a map of the continents of earth As part of the popularization e ort we are distributing Scott s Scienti c American article on the limits of quantum computation which contains a similar picture except quantum ier The concept of NP completeness was de ned in the 70s Last time we saw that the DUH problem given a Turing machine is there an input on which it halts in polynomial time is obviously NP complete duh We then took a look at our rst natural NP complete problem SATISFIABILITY or SAT for short We saw Cook and Levin s proof that SAT is NP complete by reduction from DUH Today we will see some more reductions 10 1 3 SAT reduces to 3SAT Though SAT is NP complete speci c instances of it can be easy to solve Some useful terminology a clause is a single disjunction a literal is a variable or the negation of a variable A Boolean formula in conjunctive normal form CNF is one which is the AND of ORs of literals Then the 2SAT problem which we saw earlier in the course is de ned as follows Given a CNF formula where every clause involves at most 2 literals does it have a satisfying assignment In Lecture 2 we saw that 2SAT is solvable in polynomial time because we can draw the impli cation graph and check it for cycles in polynomial time Today we ll talk about the 3SAT problem Given a CNF formula where every clause involves at most 3 literals does it have a satisfying assignment Unlike 2SAT the 3SAT problem appears to be hard In fact 3SAT is NP complete this special case encapsulates all the di culty of generic SAT To prove this we ll show how to convert an arbitrary Boolean formula into a 3SAT problem in polynomial time Thus if we had an oracle for 3SAT then we could solve SAT by converting the input into 3SAT form and querying the oracle So how do we convert an arbitrary Boolean formula into a 3SAT formula Our rst step will be to convert the formula into a circuit This is actually really straightforward every or in the formula becomes a NOT AND or OR gate in the circuit One detail we need to take care of is that when we say multiple literals ed or ed together we rst need to specify an order in which to take the s or s For example if we saw x1 x2 x3 in our formula we should parse it as either x1 x2 x3 which becomes OR x1 OR x2 x3 or x1 x2 x3 which becomes OR OR x1 x2 x3 It doesn t matter which one we pick because and are both associative So every Boolean formula can be converted to an equivalent circuit in linear time This has a couple of interesting consequences First it means the problem CircuitSAT where we are given a circuit and asked if it has a satisfying assignment is NP complete Second because Cook Levin gave us a way to convert Turing Machines into Boolean formulas if we knew a bound on the run time tacking this result on gives us a way to convert Turing Machines into circuits If the Turing Machine ran in polynomial time then the conversion will only polynomial time and the circuit will be of polynomial size Ok so now we have a circuit and want to convert it into a 3SAT formula Where does the 3 come in Each gate has at most 3 wires attached to it two inputs and one output for AND and OR and one input and one output for NOT Let s de ne a variable for every gate We want to know if there is a setting of these variables such that for every gate the output has the right relationship to the input inputs and the nal output is set to true So let s look at the NOT gate Call the input x and the output y We want that if x is true then y is false and if x is false then y is true but we ve seen how to write if then statements as disjunctions So we have N OT x y x y We can do the same thing with the truth table for OR Call the inputs x1 and x2 and the output y Let s do one row If x1 is true and x2 is false then y is true We can write this as 10 2 x1 x2 y By DeMorgan s Law this is the same as x1 x2 y Taking the AND over all possibilities for the inputs we get OR x1 x2 y x1 x2 y x1 x2 y x1 x2 y And similarly for the AND gate The big idea here is that we re taking small pieces of a problem we know to be hard gates in a circuit and translating them into small pieces of a problem we re trying to show is hard CNF formulas These small pieces are called gadgets and they re a recurring theme in reduction proofs Once we ve got these gadgets we have to somehow stick them together In this case all we have to do is AND together the Boolean formulas for each of the gates and the variable for the nal output wire The Boolean formula we get from doing this is true if and only if the circuit is satis able Woo 4 3COLOR is NP complete Given a graph is there a way to color each vertex either Red Blue or Green so that no adjacent vertices end up the same color This problem is called 3COLOR and it is NP complete We ll prove it by showing a reduction from CircuitSAT So suppose we re given a circuit and we have a magic box that when given a graph says whether it has a good 3 coloring Can we make a graph that is 3 colorable i the Boolean formula is satis able We re going to need some gadgets First of all we re renaming the colors The rst piece of our graph is going to be a triangle which will serve as a palette Notice that any good 3 coloring must assign di …