TB Schardl 6.046J/18.410JNovember 6, 2009 Recitation 8ReductionsRecall from yesterday’s lecture:REDUCTIONS ARE USEFULIntuitively, suppose you have some problem A that you don’t know how to solve. If you canfind a way to reduce problem A to some problem B that you do know how to solve, then that’s justas good as finding a way to solve A in the first place. You’ve seen an example of this sort of thingalready, when we reduced maximum bipartite matching to maximum flow.Formally, suppose we have an instance of problem A that we want to solve. Suppose furtherthat we know how to transform instances of problem A into instances of problem B in polynomialtime, and we have a machine to solve instances of problem B in polynomial time. We can solve aninstance of A in polynomial time by transforming it to an instance of B, which takes polynomialtime, solving that instance of B, which also takes polynomial time, and extracting the answer toA from the answer to B in polynomial time. This is a slight generalization from the description ofreductions described yesterday. This last step is typically obvious from the original transformation,but sometimes it requires some care.Implications of ReductionsReductions also tell us about the relative difficulty of problems. If we have a way of quicklyreducing instances of A into instances of B, then solving B is theoretically at least as difficult assolving A. After all, if you can solve B, then you can solve A by using your reduction and theB solver. I believe this is why we notate the fact that A reduces to B with the notation A < Bor A ≤ B or A ≤PB. This notion is important in complexity theory. If we know that A isNP-complete, and we have a polynomial-time reduction from A to B, then we can conclude thatB is also NP-complete. You’ll see more of this in lecture next week.Some ReductionsLet’s look at some reductions between problems. Recall the following decision problems.SAT: Given some boolean formula in CNF, does it have a satisfying assignment?3-SAT: Given some boolean formula in CNF in which each clause contains 3 literals, does it havea satisfying assignment?SAT appears to be a generalization of 3-SAT and is intuitively more difficult. However, it turnsout we can reduce SAT to 3-SAT, so 3-SAT is just as hard as SAT.2Recitation 8Problem: Reduce SAT to 3-SAT.Solution: We first create a parse tree of the given boolean formula. For example, suppose we aregiven φ = (x1∧ x2) ∨ ¬((¬x1∨ x3) ∧ x4∧ ¬x5) ∧ ¬x2. The parse tree for this φ looks like the treein figure 1. After obtaining this parse tree we associate a new variable with each internal node, asshown in the same figure. Using these new variables we can write a new boolean formulaφ′= y1∧ (y1⇐⇒ (y2∧ ¬x2))∧ (y2⇐⇒ (y3∨ y4))∧ (y3⇐⇒ (x1∧ x2))∧ (y4⇐⇒ ¬y5)∧ (y5⇐⇒ (y6∧ ¬x5))∧ (y6⇐⇒ (y7∧ x4))∧ (y7⇐⇒ (¬x1∨ x3))We now have a bunch of clauses that each have at most 3 literals. We need to convert theseclauses into CNF. To do this, for each clause we will write a truth table to see when the clause istrue. For instance, if clause C1= (y1⇐⇒ (y2∧ ¬x2)), then the truth table for C1is:y1y2¬x2C10 0 0 10 0 110 1 010 1 101 0 001 0 101 1 001 1 11With this truth table we will examine each row where the value of C1is false, or where ¬C1istrue. In this example we see that¬C1=(¬y1∧ y2∧ ¬x2)∨(y1∧ ¬y2∧ x2)∨(y1∧ ¬y2∧ ¬x2)∨(y1∧ y2∧ x2)We can apply DeMorgan’s laws to this formula to obtain a version of this clause in CNF:C1= ¬(¬C1) =(y1∨ ¬y2∨ x2)∧(¬y1∨ y2∨ ¬x2)∧(¬y1∨ y2∨ x2)∧(¬y1∨ ¬y2∨ ¬x2)Recitation 83-x2-x5x1x2ᴧᴧᴧᴧv-y1y2y3y4y5y6x4-x1x3vy7Figure 1: Parse tree for boolean expression φ = (x1∧ x2) ∨ ¬((¬x1∨ x3) ∧ x4∧ ¬x5) ∧ ¬x2.Each internal node has been associated with a new variable in order to define a new φ′booleanexpression with clauses containing at most three literals.4Recitation 8x -xFigure 2: Variable gadget for 3-SAT to k-Vertex Cover reduction. The variable x in a φ for 3-SATis replaced by two nodes in a graph. One node represents the literal x, while the other representsthe literal ¬x.To finish this reduction we have to deal with the clauses that have fewer than 3 literals in them.We can use a simple padding technique on these clauses. Suppose for instance that we have someclause (x ∨ y). This clause is equivalent to (x ∨ y ∨ p) ∧ (x ∨ y ∨ ¬p) because, no matter whatvalue of p we choose, one of x or y must be true for these clauses to be true, which is exactly thecondition that satisfies the original clause. We can therefore pad clauses with 2 variables by addingan additional variable and replicating the clause appropriately. A similar technique can be used tohandle clauses with a single variable.The correctness of this reduction can be observed from the correctness of each step. We haveto verify that this reduction creates a boolean formula for 3-SAT that is polynomial in size, and thatthis process takes polynomial time. Notice that parsing the original boolean formula into the treetakes polynomial time and generates at most a binary tree. A binary tree with n leaves contains2n nodes in total, so by transforming each internal node of this tree into a new clause we create aonly a polynomial number of clauses. Transforming each clause into CNF requires examining atmost 8 entries in a truth table since each of these clauses contains at most 3 literals. Therefore thetransformation to CNF multiplies the number of clauses by at most 8. Finally the padding step atmost doubles or quadruples the number of clauses to handle clauses that were too small. Each steptakes polynomial time and multiplies the number of clauses in the formula by at most a polynomialamount, and therefore the result is polynomial in size as desired.With this reduction we have proven that 3-SAT is at least as hard as SAT. This is useful forshowing that other problems are at least as hard as SAT. Recall the following decision problem.Vertex Cover: Given an arbitrary graph, can we find a subset of k nodes in the graph such thatevery edge touches one of the nodes in this subset?Problem: Reduce 3-SAT to Vertex Cover.Solution: Suppose our boolean formula for 3-SAT, φ, contains m variables and l clauses. Forour vertex cover we will use k = m + 2l. We will use the following two gadgets to performour reduction. For each variable in φ we will use the variable