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 Scribe: Yinmeng Zhang 1 Administrivia Work hard on the homework, but don’t freak out. Come to office 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. PNPNP-completeNP-hardOne 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 effort we are distributing Scott’s Scientific American article on the limits of quantum computation, which contains a similar picture, except quantum-ier. The concept of NP-completeness was defined 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 first “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-13 SAT reduces to 3SAT Though SAT is NP-complete, specific 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 defined as follows: • Give n a CNF formula where every clause involves at most 2 literals, does it have a satis fying 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. • Give n a CNF formula where every clause involves at most 3 literals, does it have a satis fying assignment? Unlike 2SAT, the 3SAT problem appears to be hard. In fact, 3SAT is NP-complete — this special case encapsulates all the difficulty 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 first 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 first 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 define a variable for every gate. We want to know if there is a setting of these variables such that for e very gate, the output has the right relationship to the input/inputs, and the final 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 NOT : (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 c an write this as 10-24 ( (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 final output wire. The Boolean formula we get from doing this is true if and only if the circuit is satisfiable. Woo. 3COLOR is NP-complete • Give n 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 iff the Boolean formula is satisfiable? We’re going to need some gadgets. First of all, we’re renaming the colors. The first piece of our graph is going to be a