What is reduction in computational complexity theory

Problems from NP and the polynomial reduction

Transcript

1 Problems from NP and the Polynomial Reduction Prof. Dr. Berthold Vöcking Chair of Computer Science 1 Algorithms and Complexity RWTH Aachen December 15, 2009 Berthold Vöcking, Computer Science 1 () Lecture Computability and Complexity December 15/19

2 Optimization Problems and their Decision Variants In the backpack problem (KP) we are looking for a subset K of N given objects with weights w 1, ..., w N and utility values ​​p 1, ..., p N, so that the objects from K into Backpack with weight barrier b fit and the benefit is maximized. Problem (backpack problem, Knapsack problem KP) Input: b N, w 1, ..., w N {1, ..., b}, p 1, ..., p NN permissible solutions: K {1, .. ., N}, so that i K wib Objective function: Maximize i K pi Decision variant: Let p N be given. Is there a feasible solution with utility at least p? Berthold Vöcking, Informatik 1 () Lecture Computability and Complexity December 15th / 19th

3 Optimization Problems and Their Decision Variants With the bin packing problem we are looking for a distribution of N objects with weights w 1, ..., w N over the smallest possible number of containers with weight capacity each b. Problem (Bin Packing Problem BPP) Input: b N, w 1, ..., w N {1, ..., b} permissible solutions: k N and Fkt f: {1, ..., N} {1 , ..., k}, so that i {1, ..., k}: wjbjf 1 (i) Objective function: Minimize k (= number of containers) Decision variant: k N is given. Do the objects fit in k containers? Berthold Vöcking, Informatik 1 () Lecture Computability and Complexity December 15th / 19th

4 Optimization Problems and Their Decision Variants With the TSP a complete graph of N nodes (locations) with edge weights (costs) is given. We are looking for a round trip (a Hamilton circle, a tour) with the lowest possible cost. Problem (Traveling Salesperson Problem TSP) input: c (i, j) N for i, j {1, ..., N} with c (j, i) = c (i, j) feasible solutions: permutations π on { 1, ..., N} Objective function: Minimize N 1 i = 1 c (π (i), π (i + 1)) + c (π (n), π (1)) Decision variant: b N is given. Is there a tour of length b at most? Berthold Vöcking, Informatik 1 () Lecture Computability and Complexity December 15th / 19th

5 Certificate & Verifier for Optimization Problems Theorem The decision variants of KP, BPP and TSP are in NP. Proof: Decision variants of opt. Problems have a natural candidate for a certificate, namely admissible solutions. It must be shown, however, that these solutions have a coded length that is polynomially restricted in the input length, and that their admissibility can be checked by a polynomial time algorithm. Berthold Vöcking, Informatik 1 () Lecture Computability and Complexity December 15th / 19th

6 Certificate & Verifier for Optimization Problems KP: The subset K {1, ..., N} can be coded with N bits. Given K, compliance with the weight and utility value bound can be checked in polynomial time. BPP: The mapping f: {1, ..., N} {1, ..., k} can be coded with O (N log k) bits. Given f, compliance with the weight limits can be checked in polynomial time. TSP: O (N log N) bits are required for coding a permutation π. It can be checked in polynomial time whether the round trip described by π complies with the specified cost limit b. Berthold Vöcking, Informatik 1 () Lecture Computability and Complexity December 15th / 19th

7 Optimization problem versus decision problem With the help of an algorithm that solves an optimization problem, one can obviously also solve the decision variant. (How?) Often the opposite way also works. We illustrate this with the example of KP. In the exercises we show the same for TSP and BPP. Theorem If the decision variant of KP is solvable in polynomial time, then so is the optimization variant. Berthold Vöcking, Informatik 1 () Lecture Computability and Complexity December 15th / 19th

8 Proof: Decision variant Intermediate variant Intermediate variant: We are not looking for an optimal solution, only the optimal objective function value. Polynomial time algorithm for the intermediate variant We use a binary search with the following parameters: The minimum profit is 0. The maximum profit is P: = N p i. We find the optimal objective function value by binary search on the value range {0, P}. Let A be a polynomial time algorithm for the decision variant of KP. In each iteration we use algorithm A, which tells us in which direction to look further. i = 1 Berthold Vöcking, Informatik 1 () Lecture Computability and Complexity December 15th / 19th

9 Proof: decision variant intermediate variant The number of iterations of the binary search is log (p + 1). We have to relate this number to the input length n. Lower bound for the input length: The coding length of a N is κ (a): = log (a + 1). The function κ is subadditive, i.e. for all a, b N we have κ (a + b) κ (a) + κ (b). The input length n is thus at least (N N) κ (p i) κ p i = κ (p) = log (p + 1). i = 1 i = 1 So n calls to A are sufficient to determine the optimal objective function value. Berthold Vöcking, Informatik 1 () Lecture Computability and Complexity December 15th / 19th

10 Proof: Intermediate Variant Optimization Variant From an algorithm B for the intermediate variant, we now construct an algorithm C for the optimization variant. Algorithm C 1 K: = {1, ..., N}; 2 p: = B (K); 3 for i: = 1 to N do if B (K \ {i}) = p then K: = K {i}; 4 Edition K. Runtime: N + 1 calls of algorithm B, i.e. polynomial restricted, if the runtime of B is polynomial restricted. Berthold Vöcking, Informatik 1 () Lecture Computability and Complexity December 15th / 19th

11 Polynomial Reduction Definition (Polynomial Reduction) Let L 1 and L 2 be two languages ​​over Σ 1 and Σ 2. L 1 is polynomially reducible to L 2 if there is a reduction from L 1 to L 2 that can be calculated in polynomial time is. We write L 1 p L 2. That is, L 1 p L 2, if and only if there is a function f: Σ 1 Σ 2 with the following properties: f is computable in polynomial time x Σ 1: x L 1 f (x) L 2 Berthold Vöcking, Informatik 1 () Lecture Computability and Complexity December 15th / 19th

12 Polynomial Reduction Lemma L 1 p L 2, L 2 P L 1 P. Proof: The reduction f has the polyn. Runtime bound p (). Let B be an algorithm for L 2 with polyn. Runtime bound q (). Algorithm A for L 1: 1 Compute f (x). 2 Start algorithm B for L 2 on f (x). Step 1 has a running time at most p (x). Step 2 has a running time at most q (f (x)) q (p (x) + x). Berthold Vöcking, Informatik 1 () Lecture Computability and Complexity December 15th / 19th

13 Example of a polyn. Reduction: COLORING p SAT The real strength of the reduction principle is that problems of various kinds can be reduced to one another. Problem (node ​​coloring COLORING) Input: Graph G = (V, E), number k {1, ..., V} Question: Is there a coloring c: V {1, ..., k} of the nodes of G with k colors such that neighboring nodes are different colors, i.e. {u, v} E: c (u) c (v). Problem (satisfiability problem / SAT) Input: propositional formula φ in CNF Question: Is there a fulfilling assignment for φ? Berthold Vöcking, Informatik 1 () Lecture Computability and Complexity December 15th / 19th

14 Example of a polyn. Reduction: COLORING p SAT sentence COLORING p SAT. Proof: We describe a polynomially computable function f, which maps an input (G, k) for the COLORING problem to a formula φ for the SAT problem, with the property G has a k-coloring φ is satisfiable. Berthold Vöcking, Informatik 1 () Lecture Computability and Complexity December 15th / 19th

15 Example of a polyn. Reduction: COLORING p SAT Description of the function f: The formula φ has a variable xv i for every node-color combination (v, i), v V, i {1, ..., k}. The formula for (G, k) is φ = (xv 1 x2 v ... xk v). v V} {{} node condition (xiu xi v)} {{} {u, v} E i {1, ..., k} edge condition number of literals = O (k V + k E) = O (V 3 ). The length of the formula is therefore polynomially restricted and the formula can be constructed in polynomial time. But is the construction correct? Berthold Vöcking, Informatik 1 () Lecture Computability and Complexity December 15th / 19th

16 Example of a polyn. Reduction: COLORING p SAT Correctness: zz: G has k coloring φ is satisfiable Let c be k coloring for G. For every node v with c (v) = i we set xv i = 1 and all other variables to 0. Node condition: Obviously fulfilled. Edge condition: x i u x i v holds for every color i and every edge {u, v}, because otherwise u and v would both have the color i. This assignment thus fulfills the formula φ. Berthold Vöcking, Informatik 1 () Lecture Computability and Complexity December 15th / 19th

17 Example of a polyn. Reduction: COLORING p SAT zz: φ is satisfiable G has a k coloring Fix any satisfying assignment for φ. Because of the node condition there is at least one color for each node v with x i v = 1. For each node choose any such color. Let {u, v} E. We claim c (u) c (v). As a contradiction, we assume that c (u) = c (v) = i. Then x i u = x i v = 1 and the edge condition x i u x i v would be violated. Berthold Vöcking, Informatik 1 () Lecture Computability and Complexity December 15th / 19th

18 Example of a polyn. Reduction: COLORING p SAT COLORING p SAT implies the following two statements. Corollary If SAT has a polynomial time algorithm, COLORING also has a polynomial time algorithm. Berthold Vöcking, Informatik 1 () Lecture Computability and Complexity December 15th / 19th

19 Outlook A problem L NP is called NP-complete if for every problem L NP we have L p L. Theorem (Levin and Cook) SAT is NP-complete. It follows: If SAT had a polynomial time algorithm, there would also be a polynomial time algorithm for every other problem from NP, and thus P = NP. Conversely, the following applies: SAT has no polynomial time algorithm unless P = NP. Berthold Vöcking, Informatik 1 () Lecture Computability and Complexity December 15th / 19th