=========================================================================== CSC 363H Lecture Summary for Week 12 Summer 2007 =========================================================================== ----------------- Self-reducibility ----------------- Note: This material is not in the textbook. This summary will therefore be slightly more detailed than usual. Problem of deciding language A sometimes called "decision problem": given input x, solution = yes/no answer. But many problems are more naturally "search problems": given input x, find solution y. Examples: - Given prop. formula F, find satisfying assignment, if one exists. - Given graph G, integer k, find a clique of size k in G, if one exists. - Given graph G, find a Ham. path in G, if one exists. - Given set of numbers S, target t, find subset of S whose sum equals t, if one exists. - etc. Many languages come from natural search problems. Clearly, efficient solution to search problem would give efficient solution to corresponding decision problem. So proof that decision problem is NP-hard implies that search problem is "NP-hard" as well (in some generalized sense of NP-hard), and does not have efficient solution. But exactly how much more difficult are search problems? Perhaps surprisingly, many are only polynomially more difficult than corresponding decision problem, in the following sense: any efficient solution to the decision problem can be used to solve the search problem efficiently. This is called "self-reducibility". Example 1: SAT Input: formula f Decision: YES, if f is satisfiable; NO ow Search: v, a satisfying assignment for f, if one exists; NIL ow Assume we have an algorithm SAT for the decision problem that works in polynomial time t(n). We construct an algorithm for the search problem that also runs in polynomial time. Idea: try setting variables to either TRUE or FALSE, simplify the formula, check if it is still satisfiable. For a formula f, let f[x=TRUE] denote f with every occurence of variable x replaced by TRUE (and not(x) replaced by FALSE) and simplified according to boolean logic rules. E.g. f = (x_1 and (not(x_2) or x_3)) or (not(x_1) and x_2) then, f[x_2=FALSE] = (x_1 and (not(FALSE) or x_3)) or (not(x_1) and FALSE) = (x_1 and (TRUE or x_3)) or FALSE = (x_1 and TRUE) = x_1 SAT-SEARCH: input: formula f if SAT(f) = NO, output NIL // f is not satisfiable let the variables of f be x_1, ..., x_m for i <- 1 to m f' <- f[x_i=TRUE] if SAT(f')=YES, v_i <- TRUE f <- f' else v_i <- FALSE f <- f[x_i=FALSE] endif endfor output v Let f_i be the formula f after the i-th iteration of the loop. Let f_0 be the input formula. Invariant: for all i, (i) f_i is satisfiable (ii) f_i = f[x_j = v_j for all j <= i] Base case: i = 0 - f_0 is satisfiable because otherwise the answer would be NIL - The second condition says nothing because there are no indices j <= 0 Inductive step: assume invariant holds for i-1 - Since f_{i-1} is satisfiable, there exists an assignment that satisfies it. In this assignment, x_i is assigned either TRUE or FALSE. Thus, either f_{i-1}[x_i=TRUE] or f_{i-1}[x_i=FALSE] is satisfiable. The algorithm continues with f_i being one of these only if it is satisfiable. - Clearly, the value remembered in v_i is the value used to obtain f_i from f_{i-1}. At the end: By (i), f_m is satisfiable. But there are no more variables left, so f_m=TRUE. By (ii), f_m = f[x_j = v_j forall j]. Thus, v is a satisfying assignment for f. Running time: - n is the size of the original formula; - all calls to SAT are on formulas of size <= n, so they take <= t(n); - one simplification of the form f' <- f[x=TRUE] can be done in time O(n^2) because the number of literals appearing in f is <=n and each time we get rid of a TRUE or a FALSE, we reduce the number of literals. - in total, runtime is: t(n) + n*( O(n^2) + t(n) + O(n^2)) = O( (n+1)*t(n) + n^3 ) - if t(n) is polynomial in n, so is the runnint time of SAT-SEARCH Example 2: 3-SAT Input: 3-CNF formula f Decision: YES, if f is satisfiable; NO ow Search: v, a satisfying assignment for f, if one exists; NIL ow Assume we have a polytime algorithm for 3-SAT-DECISION. Can we use the exact same construction to get an algorithm for 3-SAT-SEARCH? The answer is NO. After a simplification f' <- f[x=TRUE], there is no guarantee that f' is still a 3-CNF formula. Thus, we cannot simply run 3-SAT on f'. There is a quick fix for this, however. If f is a 3-CNF formula, f' will also be a CNF formula with clauses of sizes 1, 2 or 3. We can artificially bump it back to being a 3-CNF formula by repeating literals in clauses of sizes 1 or 2. This does not change the truth value of f', but it allows us to use the 3SAT algorithm for the decision problem. Thus, almost the same construction (plus the extra fix we talked about) can be used to solve 3-SAT-SEARCH given a solution to 3-SAT-DECISION. Example 3: 3-SYMM-SAT Input: 3-CNF formula f Decision: YES, if there is a symmetrically-satisfying assignment for f; NO, ow Search: v, a symmetrically-satisfying assignment for f, if one exists; NIL, ow Definition: Let f be a 3-CNF formula. A symmetrically-satisfying assignment for f is an assignment under which every clause has one literal evaluating to TRUE and one literal evaluating to FALSE. Can the construction of SAT-SEARCH from SAT-DECISION be adapted to work in this case? Probably not. This construction pays no attention to the requirement that there is a FALSE literal in every clause. Idea: We still want to simplify the formula f, by removing variables and remembering a suitable truth value for them. In this case, we will apply the same idea, but rather than erasing a variable, we will replace it with a special extra variable y, or with its negation not(y). For any formula f, let f[x<-y] denote the formula obtained by replacing each occurence of x with y and each occurence of not(x) with not(y). 3-SYMM-SAT-SEARCH: input: 3-CNF formula f if 3-SYMM-SAT-DECISION(f) = NO, output NIL let the variables of f be x_1 ... x_m f <- f AND (y OR y OR not(y)) // note that f is at this point 3-CNF and symmetrically satisfiable for i <- 1 to m f' <- f[x_i<-y] if 3-SYMM-SAT-DECISION(f') = YES, v_i <- TRUE f <- f' else v_i <- FALSE f <- f[x_i<-not(y)] endif endfor output v Let f_i be the formula f after the i-th iteration of the loop. Let f_0 be the input formula plus the extra clause. Invariant: for all i, (i) f_i is symmetrically satisfiable; and (ii) f_i = f[for all j<=i, x_j<-y if v_j=TRUE and x_j<-not(y) if v_j=FALSE] Base case: i = 0 - f_0 is symmsat, otherwise the answer would have been NIL - part (ii) says nothing, as there are no indices j<=0 Inductive step: assume the invariant holds for i-1 - Let w be a symmsat assignment for f_{i-1}. In it, the variables x_i and y are either assinged the same truth value, or different values. Depending on this, either f[x_i<-y] or f[x_i<-not(y)] is symmsat. The algorithm continues with f_i being one of these only if it is symmsat. - The value v_i remembered for x_i is TRUE iff x_i is replaced by y in f_i. At the end: i = m By (i), f_m is symmsat. But f_m is a 3-CNF formula with only one variable, y. Thus, each clause contains a y and a not(y). By (ii), for every literal l appearing in some clause of f, the truth value of l under v is TRUE iff that literal is replaced with y in f_m. Since in f_m every clause contains a y and a not(y), we conclude that in f under v every clause has a literal made TRUE and a literal made FALSE. Example 4: VERTEX-COVER-SEARCH Input: Graph G, integer k. Output: A vertex cover of size k, if one exists (NIL otherwise). - Idea 1: Remove vertices one-by-one as long as resulting graph still contains a vertex cover of size k. - Problem: If G contains a VC of size k, then G-v (remove v and all incident edges) also contains a VC of size k, whether or not v is in the cover (unless k=n, trivial to solve)! - Idea 2: If node v is included in the cover, it will cover all edges that are incident to v. So, if (G - edges connected to v) has a v.c. of size k-1, we can get a v.c. of G by throwing v in. - Algorithm: VCS(G,k): if VC(G,k) = NO, return NIL C = {} # the vertices in a vertex cover of G let the vertices of G be v_1 ... v_m for i <- 1 to m and while k > 0: G' = G - {all edges touching v_i} if VC(G', k-1) = YES, C = C U {v_i}; G = G'; k = k - 1 return C - Let G_i, C_i, k_i be the values of G, C, k at the end of the i-th iteration of the loop. - Loop invariant: for all i, (i) G_i contains a vertex cover of size >=k_i, USING ONLY VERTICES FROM { v_{i+1} ... v_m } (THIS PART WE DIDN'T USE IN CLASS, BUT IT'S USEFUL FOR PROVING CORRECTNESS) (ii) C_i is a vertex cover of (G_0 - G_i) of size (k_0 - k_i) - Base case: i = 0, - G_0 has a v.c. of size k_0 using vertices from { v_1 ... v_m } = V because otherwise the output would be NIL. - C_0 is empty, but there are no edges in (G_0 - G_0). - Inductive step: assume the invariant holds for i-1, case 1: if the call VC(G',k-1) returns NO: The variables G_i, C_i, k_i do not change from their previous values, so one could incline towards saying that the invariant continues to hold. There is one subtle point here: i itself changes, and this might invalidate the latter part of (i). Specifically, assume (i) becomes false. That is, G_i does NOT contain a v.c. of size k_i using { v_{i+1} ... v_m }. By the induction hypothesis, G_{i-1}=G_i contains a v.c. of size k_{i-1}=k_i using vertices from { v_i ... v_m }. The only way these things are possible is when there exists a v.c. of G_i of size k_i that uses vertex v_i (it's the only one that is no longer available after iteration i). However, in that case, there exists a cover of G' = (G_i - {edges touching v_i}) of size k_i-1! This contradicts the fact that we are in case 1. Hence, (i) continues to hold. Trivially, (ii) continues to hold as it does not depend on i, only on C_i and G_i, which do not change. case 2: if the call VC(G',k-1) returns YES: G_i <- G_{i-1} - {edges touching v_i} C_i <- C_{i-1} + v_i k_i <- k_{i-1} - 1 By the induction hypothesis, there is a v.c. of G_{i-1} of size k_{i-1} using only vertices from { v_i ... v_m }. Call it B. If v_i is in B, then B-v_i is a vertex cover of G_i of size k_i = k_{i-1}-1 using only vertices from { v_{i+1} ... v_m }. If v_i is not in B, then B is a vertex cover of G_i of size >=k_{i-1}>k_i using only vertices from { v_{i+1} ... v_m }. Either way, G_i has a vertex cover of size >=k_i with vertices from { v_{i+1} ... v_m }. This shows (i). For (ii), the node v_i that we are adding to C_i can be used to cover the new edges from (G_0 - G_i) not already in (G_0 - G_{i-1}), namely, the ones that get deleted in this iteration. - At the end: i = m or k = 0. If k = 0, by (i) G_i has a vertex cover of size k_i=0. This is only possible if G_i has no edges. Thus, (G_0 - G_i) = G_0. By (ii), C_i has a vertex cover of G_0 of size k_0 - k_i = k_0. If i = m, by (i) G_m has a vertex cover of size k_m using only vertices from { v_{m+1} ... v_m }, but this set is empty! NOTE: IT IS HERE THAT WE USE THE EXTRA CONDITION. Thus, G_m has an empty vertex cover, which means that it is empty! Again, (G_0 - G_m) = G_0. By (ii), C_m is a vertex cover of G_0 of size k_0 - k_m <= k_0. If we really need a vertex cover of size k_0, we can simply add another k_m arbitrary vertices, C_m will continue being a vertex cover. - Runtime: O((n+1)*t(n,m) + n*(n+m)) -- for each vertex v, we perform one call to VC in time t(n,m) and compute G-v in time O(n+m).