08np.ppt

Transcription

1 CSE 417, Winter 2012 P, NP, and Intractability Ben Birnbaum Widad Machmouchi Slides adapted from Larry Ruzzo and Kevin Wayne! 1

2 The Simpson's: P = NP? Copyright 1990, Matt Groening 2

3 Looking for a Job? Some writers for the Simpsons and Futurama. J. Steward Burns. M.S. in mathematics, Berkeley, David X. Cohen. M.S. in computer science, Berkeley, Al Jean. B.S. in mathematics, Harvard, Ken Keeler. Ph.D. in applied mathematics, Harvard, Jeff Westbrook. Ph.D. in computer science, Princeton,

4 What can we feasibly compute? Focus so far in the course has been to give good algorithms for specific problems (and general techniques that help do this). Now shifting focus to problems where we think this is impossible. 4

5 Overview Researchers found many problems with obvious exponential solutions, but no polynomial time algorithm known. Eventually, researchers gave up and started trying to prove that it was impossible to solve these problems efficiently. Didn t quite succeed here either. However, they did develop a beautiful theory that allows us to show that many problems probably can t be solved efficiently. Theory of NP-Completeness 5

6 Our goals 1. Explain how this theory works. 2. Show how to use it to prove a problem is probably not solvable in polynomial time. This is the most theoretical part of the course, but it is very important. 6

7 Polynomial versus exponential Polynomial Bigger than polynomial 7

8 Polynomial vs Exponential Growth 2 2n! 2 2n 2 n/10 2 n/10! 1000n n 2! 8

9 Another view of Poly vs Exp Next year's computer will be 2x faster. If I can solve problem of size n 0 today, how large a problem can I solve in the same time next year? Complexity Increase E.g. T=10 12 O(n) n 0 à 2n x O(n 2 ) n 0 à 2 n x 10 6 O(n 3 ) n 0 à 3 2 n x n /10 n 0 à n n n 0 à n

10 Polynomial versus exponential Of course there are exceptions: n 100 is bigger than (1.001) n for most practical values of n but usually such run-times don t show up There are algorithms that have run-times like O(2 sqrt(n)/22 ) and these may be useful for small input sizes, but they're not too common either 10

11 Decision problems Computational complexity usually analyzed using decision problems: answer just YES or NO (1 or 0) Example: Find the minimum spanning tree è Is there a spanning tree of size k? Why? Much simpler to deal with Deciding whether G has a k-clique is certainly no harder than finding a k-clique in G or finding the size of the maximum k- clique. So proving decision problem is hard is a strong result. Less important, but if you have a good decider, you can often use it to get a good finder. 11

12 Some Decision Problems Independent-Set: Given a graph G=(V,E) and an integer k, is there a subset U of V with U k such that no two vertices in U are joined by an edge. Clique: Given a graph G=(V,E) and an integer k, is there a subset U of V with U k such that every pair of vertices in U is joined by an edge. 12

13 Some Terminology "Problem" the general case Ex: The Clique Problem: Given a graph G and an integer k, does G contain a k-clique? "Problem Instance" the specific cases Ex: Does instance contain a 4-clique? This is a NO Ex: Does instance contain a 3-clique? This is a YES 13

14 The class P Definition: P = set of (decision) problems solvable by computers in polynomial time. i.e., T(n) = O(n k ) for some fixed k (indp of input). These problems are sometimes called tractable problems. Examples: shortest path, MST, connectivity, interval scheduling, dynamic programming most of this quarter 14

15 Beyond P? There are many natural, practical problems for which we don t know any polynomial-time algorithms 15

16 Some Examples Independent-Set: Given a graph G=(V,E) and an integer k, is there a subset U of V with U k such that no two vertices in U are joined by an edge. Clique: Given a graph G=(V,E) and an integer k, is there a subset U of V with U k such that every pair of vertices in U is joined by an edge. 16

17 Some Examples Vertex-Cover: Given a graph G=(V,E) and an integer k, is there a subset U of V with U k such that every edge touches a vertex in U. 17

18 Some Examples Hamiltonian Cycle: Given a graph G = (V, E), is there a cycle that visits each node exactly once? 18

19 Some Examples Hamiltonian Cycle: Given a graph G = (V, E), is there a cycle that visits each node exactly once? YES NO 19

20 Some Examples Traveling Salesperson Problem: Given a weighted graph G=(V,E,w) and an integer k, is there a Hamiltonian cycle with total weight k? 20

21 Traveling Salesperson Problem TSP. Given a weighted graph G=(V,E,w) and an integer k, is there a Hamiltonian cycle with total weight k? All 13,509 cities in US with a population of at least 500 Reference: 21

22 Traveling Salesperson Problem TSP. Given a weighted graph G=(V,E,w) and an integer k, is there a Hamiltonian cycle with total weight k? Optimal TSP tour Reference: 22

23 Satisfiability Boolean Formulas Boolean variables x 1,..., x n taking values in {0,1}. 0=false, 1=true Literals x i or x i for i = 1,..., n Clause a logical OR of one or more literals e.g. (x 1 x 3 x 7 x 12 ) CNF formula ( conjunctive normal form ) a logical AND of a bunch of clauses 23

24 Satisfiability CNF formula example (x 1 x 2 x 4 ) ( x 1 x 2 x 3 x 4 ) If there is some assignment of 0 s and 1 s to the variables that makes it true then we say the formula is satisfiable the one above is, the following isn t x 1 ( x 1 x 2 ) ( x 2 x 3 ) x 3 Satisfiability: Given a CNF formula F, is it satisfiable? 24

25 Satisfiable? ( x y z ) ( x y z ) ( x y z ) ( x y z ) ( x y z ) ( x y z ) ( x y z ) ( x y z ) ( x y z ) ( x y z ) ( x y z ) ( x y z ) ( x y z ) ( x y z ) ( x y z ) ( x y z ) 25

26 History As of 1970 Many of the above problems had been studied for decades. All had real, practical applications. None were known to be in P. Exponential algorithms were the best known. It turns out they all have a very deep similarity under the skin. They all belong to a class of problems called NP. 26

27 NP: problems with efficient verifiers Verification algorithm intuition: Verifier views things from "managerial" viewpoint. Verifier doesn't determine whether a problem instance is YES on its own. Rather, it checks a proposed proof (certificate) that an instance is YES. NP stands for nondeterministic polynomial time 27

28 The complexity class NP NP consists of all decision problems where And You can verify the YES answers efficiently (in polynomial time) given a short (polynomial-size) certificate No certificate can fool your polynomial time verifier into saying YES for a NO instance 28

29 Precise Definition of NP A decision problem is in NP iff there is a polynomial time procedure v(-,-), and an integer k such that for every YES problem instance x there is a certificate h with h x k such that v(x,h) = YES and for every NO problem instance x there is no certificate h with h x k such that v(x,h) = YES 29

30 Example: CLIQUE is in NP procedure v(x,h) if x represents a graph G and h represents a set of vertices U. and there is an edge in G between each pair of vertices in U then output YES else output NOT CONVINCED 30

31 Is it correct? For every x = (G,k) such that G contains a k-clique, there is a certificate h that will cause v(x,h) to say YES, namely h = a list of the vertices in such a k- clique and No certificate can fool v into saying yes if either x isn't well-formed (the uninteresting case) or if x = (G,k) but G does not have any cliques of size k (the interesting case) 31

32 Another example: SAT NP Certificate: the satisfying assignment A Verifier: v(f,a) = syntax(f,a) && satisfies(f,a) Syntax: True iff F is a well-formed formula & A is a truth-assignment to its variables Satisfies: plug A into F and evaluate Correctness: If F is satisfiable, it has some satisfying assignment A, and we ll recognize it If F is unsatisfiable, it doesn t, and we won t be fooled 32

33 Keys to showing that a problem is in NP What's the output? (must be YES/NO) First, describe the certificate and verifier. Second, for every YES instance, show that there is a certificate that would cause the verifier to output YES in polynomial time. Third, for every NO instance, show that there is no certificate that would cause the verifier to output YES, i.e. the verifier can t be tricked. 33

34 Another Example: Hamiltonian Cycle NP Certificate: a list of the vertices in the cycle Verifier: check that inputs are well-formed, that there is an edge between each of the vertices in certificate, and that every vertex appears exactly once. Correctness: If YES instance: then there is a certificate corresponding to a Hamiltonian cycle, and verifier outputs YES in polynomial time. If NO instance: no certificate will fool the verifier. 34

35 Are all problems in NP? No, think about Tautology: given a boolean formula, decide whether it is always true. Not clear what a certificate would look like. How would one efficiently show (or check) that all assignments evaluate to true? 35

36 Review Described move from optimization to decision problems Described complexity class P Described complexity class NP Showed that a bunch of problems are in NP Next up: NP who cares? In the book: 8.3 -> 8.1 -> 8.2 ->

37 P vs. NP If a problem is in P, then we can construct a verifier that ignores the certificate and just solves the problem. This verifier satisfies our requirements for being in NP. Thus, P NP 37

38 Example: Graph Connectivity Graph-Connectivity: Is graph G = (V, E) connected? Certificate: Verifier: Ignore certificate. Run BFS (or DFS) to determine if graph is connected. If so, output YES. Else, output NOT CONVINCED. 38

39 Proving Connectivity is in NP First, for every YES instance, the verifier outputs YES given the certificate Second, for every NO instance, the verifier will never output YES, no matter what the certificate is. So Graph-Connectivity is in NP. This works for any problem in P. Hence, P NP 39

40 Complexity Classes! NP = Polynomial-time verifiable!! P = Polynomial-time solvable!! NP P P NP 40

41 P vs. NP But does P = NP? How would we answer this question? Yes: provide a polynomial time algorithm for every problem in NP No: find just one problem in NP and prove there is no polynomial time algorithm for it Doing either of these is worth $1M 41

42 But a beautiful theory was developed NP-complete: the hardest problems in NP As long as P NP (seems likely), there is no polynomial time algorithm for any NPcomplete problem We can show that lots of problems are NPcomplete SAT, Clique, Vertex Cover, Independent Set, TSP, etc. 42

43 But a beautiful theory was developed NP-complete: the hardest problems in NP What does it mean for one problem to be harder than another? Before defining NPcomplete, we need to define this: Polynomial-Time Reductions 43

44 Reductions: a useful tool Intuitive Definition: To reduce A to B means to solve A, given a black box subroutine solving B. 44

45 Reducing MEDIAN to SORT Algorithm for MEDIAN Input: list of numbers Call sort alg Output item n/2 Output: median Black Box algorithm for sort Since we can use alg for SORT to solve MEDIAN, SORT is at least as hard as MEDIAN 45

46 More reductions Example: reduce MEDIAN to SORT Solution: sort, then select (n/2)nd Example: reduce SORT to FIND_MAX Solution: FIND_MAX, remove it, repeat Example: reduce MEDIAN to FIND_MAX Solution: transitivity: compose solutions above. 46

47 Interlude: some notation Let A be a problem and x be an input to A. If x is a YES instance, we write x A If x is a NO instance, we write x A Comes from a more formal treatment of this material, in which problems can be thought of as sets of strings. 47

48 If you want to learn more 48

49 Polynomial-Time Reductions Let A and B be two problems. We say that A is polynomially reducible to B (A p B) if there exists a polynomial-time algorithm f that converts each instance x of problem A to an instance f(x) of B such that: x is a YES instance of A iff f(x) is a YES instance of B x A f(x) B Sometimes the direction of this inequality confuses people 49

50 Why p notation? Define: A p B A is polynomial-time reducible to B, iff there is a polynomial-time computable function f such that: x A f(x) B complexity of A complexity of B + complexity of f 50

51 A p B pictorially Algorithm to solve A x Algorithm to compute f f(x) Algorithm f(x) B? x A? to solve B 51

52 Example: Vertex Cover P Set Cover SET COVER: Given a set U of elements, a collection S 1, S 2,..., S m of subsets of U, and an integer k, does there exist a collection of k of these sets whose union is equal to U (i.e. that cover U)? Ex: U = { 1, 2, 3, 4, 5, 6, 7, 8, 9 } k = 3 S 1 = {1, 7, 8, 9} S 4 = {2, 4, 9} S 2 = {3, 4, 5, 6} S 5 = {5, 8} S 3 = {1} S 6 = {1, 2, 6, 7} Sample application. m available pieces of software. Set U of n capabilities that we would like our system to have. The i-th piece of software provides the set S i U of capabilities. Goal: achieve all n capabilities using fewest pieces of software. 52

53 Example: Vertex Cover P Set Cover Vertex Cover P Set Cover because Set Cover is a generalization of Vertex Cover VERTEX COVER a b e 7 e 2 e 3 e 4 f e 6 c k = 2 e 1 e d e 5 SET COVER f(x) U = { 1, 2, 3, 4, 5, 6, 7 } k = 2 S a = {3, 7} S b = {2, 4} S c = {3, 4, 5, 6} S d = {5} S e = {1} S f = {1, 2, 6, 7} 53

54 Example: Vertex Cover P Set Cover Claim. Vertex Cover P Set Cover. Pf. Given a Vertex Cover instance x = (G = (V, E), k), we construct a Set Cover instance f(x) as follows: k = k, U = E, S v = {e E : e incident to v } f(x) can be computed in polynomial time. x Vertex Cover iff f(x) Set Cover, because there is set cover of size k iff vertex cover of size k. VERTEX COVER a b SET COVER k = 2 f e 7 e 1 e 2 e 3 e 6 e d e 4 e 5 c U = { 1, 2, 3, 4, 5, 6, 7 } k = 2 S a = {3, 7} S b = {2, 4} S c = {3, 4, 5, 6} S d = {5} S e = {1} S f = {1, 2, 6, 7} 54

55 Why do we care about reductions? We ll see plenty more reductions, but let s come back to the big picture first. 55

56 What does a reduction tell us? Observation: p(x) and q(x) polynomials, then p(x) + q(x) is polynomial (1) A p B and B P A P (2) A p B and A P B P (3) A p B and B p C A p C (transitivity) 56

57 Definition of NP-Completeness Definition: Problem B is NP-hard if every problem in NP is polynomially reducible to B. Definition: Problem B is NP-complete if: (1) B belongs to NP, and (2) B is NP-hard. 57

58 Complexity Classes P = Poly-time solvable!! NP = Poly-time verifiable!! NP-Complete = Hardest problems in NP NP NP-Complete P 58

59 NP-completeness Cool concept, but are there any such problems? Yes! Cook-Levin theorem (1971): SAT is NP-complete 59

60 Why is SAT NP-complete? Proof of Cook-Levin is somewhat involved; I won t show it. But its essence is not so hard to grasp: Generic NP problem: is there a poly size solution, verifiable by computer in poly time SAT : is there a (poly size) assignment satisfying the formula Encode solution using Boolean variables. SAT mimics is there a solution via is there an assignment. Digital computers just do Boolean logic, and SAT can mimic that, too, hence can verify that the assignment actually encodes a solution. 60

61 Proving a problem is NP-complete Technically, for condition (2) we have to show that every problem in NP is reducible to B. (Yikes! Sounds like a lot of work.) For the very first NP-complete problem (SAT) this had to be proved directly. However, once we have one NP-complete problem, then we don t have to do this every time. Why? Transitivity. 61

62 Re-stated Definition Lemma: Problem B is NP-complete if: (1) B belongs to NP, and (2 ) A is polynomial-time reducible to B, for some problem A that is NP-complete. That is, to show (2 ) given a new problem B, it is sufficient to show that SAT or any other NPcomplete problem is polynomial-time reducible to B. 62

63 Usefulness of Transitivity In order to show that P is NP-hard, we only have to show P p P for some NP-hard problem P, Why? 1) Since P is NP-hard, P NP, we have P p P 2) If we show P p P, then by transitivity we know that: P NP, we have P p P. Thus P is NP-hard. 63

64 Ex: VertexCover is NP-complete SAT is NP-complete (shown by S. Cook) SAT p VertexCover (we ll show this later) VertexCover is in NP (why?) Therefore VertexCover is also NP-complete So, poly-time algorithm for VertexCover would give poly-time algs for everything in NP 64

65 NP-completeness Karp (1972): SAT p Clique, SAT p Vertex Cover, SAT p Ham Path, Since, then, thousands more problems proved NP-complete 65

66 NP-completeness If there was a polynomial time algorithm for any NP-complete problem, then P = NP. If at least one cannot be solved in polynomial time, then none could. So either all NP-complete problems have polynomial time algorithms, or none do. Since no one has ever found a polynomial time algorithm for an NP-complete problem, they are probably intractable. 66

67 What s next? Use polynomial time reductions to show that a number of problems we care about are NP-complete. Important to know how to do this, in order to determine whether you should try to solve a new problem. Later, we ask what do we do with all these NP-complete problems? 67

68 Review We defined some useful complexity classes. NP NP-hard Cook-Levin Theorem: SAT is NP-complete To prove a new problem is NP-complete, we need to show a chain of reductions from SAT P NP-complete 68

69 Reduction Tree Satisfiability Won t show Today 3-Satisfiability Independent Set Hamiltonian Cycle Today Vertex Cover Set Cover Already shown Clique TSP 69

70 NP-completeness proof outline To show a problem P is NP-complete: 1. Show it is NP (usually easy). 2. For a problem P known to be NP-complete, show that P p P. a. Provide an algorithm (function) f for transforming input of P to input of P. b. Argue that f can be computed in polynomial time (usually easy). c. Show that x P f(x) P. i. Show that x P f(x) P. ii. Show that f(x) P x P. 70

71 Independent Set INDEPENDENT SET: Given a graph G = (V, E) and an integer k, is there a subset of vertices S V such that S k, and for each edge at most one of its endpoints is in S? Ex. Is there an independent set of size 6? Yes. Ex. Is there an independent set of size 7? No. independent set 71

72 Vertex Cover VERTEX COVER: Given a graph G = (V, E) and an integer k, is there a subset of vertices S V such that S k, and for each edge, at least one of its endpoints is in S? Ex. Is there a vertex cover of size 4? Yes. Ex. Is there a vertex cover of size 3? No. vertex cover 72

73 Proving Vertex Cover NP-complete Theorem: If Independent Set is NP-complete, then Vertex Cover is NP-complete. Proof: Vertex Cover is in NP. A certificate consists of the set of vertices in the cover. It can be verified in polynomial time that such a set of vertices has the required size and does cover all edges. To finish the proof, we will show that Independent Set P Vertex Cover. 73

74 Proving Vertex Cover NP-complete Observation: S is an independent set iff V - S is a vertex cover. Let S be any independent set. Consider an arbitrary edge (u, v). S independent u S or v S u V - S or v V - S. Thus, V - S covers (u, v). Let V - S be any vertex cover. Consider two nodes u S and v S. Observe that (u, v) E since V - S is a vertex cover. Thus, no two nodes in S are joined by an edge S independent set. 74

75 Proving Vertex Cover NP-complete Theorem: If Independent Set is NP-complete, then Vertex Cover is NP-complete. Proof (continued): Given an input x = (G = (V, E), k) to Independent Set, let f(x) be the Vertex Cover input G = (V, E), n k. Clearly, f can be computed in polynomial time. By our observation, x has an independent set of size k iff f(x) has a vertex cover of size n k. Hence x Independent Set f(x) Vertex Cover. 75

76 Satisfiability Literal: A Boolean variable or its negation. x i or x i Clause: A disjunction of literals. C j = x 1 x 2 x 3 Conjunctive normal form: A propositional formula Φ that is the conjunction of clauses. Φ = C 1 C 2 C 3 C 4 SAT: Given CNF formula Φ, does it have a satisfying truth assignment? 3-SAT: SAT where each clause contains exactly 3 literals. each corresponds to a different variable ( x 1 x 2 x 3 ) ( x 1 x 2 Ex: x 3 ) x 2 x 3 Yes: x 1 = true, x 2 = true x 3 = false. ( ) ( x 1 x 2 x 3 ) 76

77 Independent Set is NP-complete Theorem. 3-SAT is NP-complete. Pf. We won t show this, but there is a reduction from SAT. Theorem. Independent Set is NP-compete. Pf. First, Independent Set is clearly in NP. A certificate would consist of the list of vertices. It could be easily verified in polynomial time that no edge has both endpoints in this list of vertices. We now show that 3-SAT P Independent Set. 77

78 3 Satisfiability Reduces to Independent Set Claim. 3-SAT P INDEPENDENT-SET. Pf. Given an instance Φ of 3-SAT, we construct an instance (G, k) of INDEPENDENT-SET that has an independent set of size k iff Φ is satisfiable. Construction. G contains 3 vertices for each clause, one for each literal. Connect 3 literals in a clause in a triangle. Connect literal to each of its negations. x 1 x 2 x 1 G k = 3 x 2 x 3 x x 1 x 2 x 3 4 Φ = ( x 1 x 2 x 3 ) ( x 1 x 2 x 3 ) ( x 1 x 2 x 4 ) 78

79 3 Satisfiability Reduces to Independent Set Claim. G contains independent set of size k = Φ iff Φ is satisfiable. Pf. Let S be independent set of size k. S must contain exactly one vertex in each triangle. Set these literals to true. and any other variables in a consistent way Truth assignment is consistent and all clauses are satisfied. Pf Given satisfying assignment, select one true literal from each triangle. This is an independent set of size k. x 1 x 2 x 1 G x 2 x 3 x x 1 x 2 x 3 4 k = 3 Φ = ( x 1 x 2 x 3 ) ( x 1 x 2 x 3 ) ( x 1 x 2 x 4 ) 79

80 Reduction Tree Satisfiability Shown 3-Satisfiability Next Shown Independent Set Hamiltonian Cycle Vertex Cover Set Cover Shown Clique TSP 80

81 Hamiltonian Cycle HAM-CYCLE: given an undirected graph G = (V, E), does there exist a simple cycle Γ that contains every node in V. YES 81

82 Hamiltonian Cycle HAM-CYCLE: given an undirected graph G = (V, E), does there exist a simple cycle Γ that contains every node in V. 1 1' 2 2' 3 3' 4 4' 5 NO 82

83 Directed Hamiltonian Cycle DIR-HAM-CYCLE: given a digraph G = (V, E), does there exists a simple directed cycle Γ that contains every node in V? Claim. DIR-HAM-CYCLE P HAM-CYCLE. Pf. Given a directed graph G = (V, E), construct an undirected graph G' with 3n nodes. a a out d in d b c v e b out v in v v out e in G c out G' 83

84 3-SAT Reduces to Directed Hamiltonian Cycle Claim. 3-SAT P DIR-HAM-CYCLE. Pf. Given an instance Φ of 3-SAT, we construct an instance of DIR- HAM-CYCLE that has a Hamiltonian cycle iff Φ is satisfiable. Construction. First, create graph that has 2 n Hamiltonian cycles which correspond in a natural way to 2 n possible truth assignments. 84

85 3-SAT Reduces to Directed Hamiltonian Cycle Construction. Given 3-SAT instance Φ with n variables x i and k clauses. Construct G to have 2 n Hamiltonian cycles. Intuition: traverse path i from left to right set variable x i = 1. s x 1 x 2 x 3 t 3k

86 3-SAT Reduces to Directed Hamiltonian Cycle Construction. Given 3-SAT instance Φ with n variables x i and k clauses. For each clause: add a node and 6 edges. C clause node 1 = x1 V x2 V x3 clause node C 2 = x1 V x2 V x3 s x 1 x 2 x 3 t 86

87 Minimum-Weight Triangulation Two triangulations of a set of five points: Weight = 22.9 Weight = 15.7 Minimum Weight Triangulation Problem: Given a set of n points in the plane, find the triangulation of minimum total weight. (Decision version: is there a triangulation of weight <= k?) Problem first posed in 1970s. Until 2006, the most longstanding open problem in computational geometry. Mulzer and Rote (2006): MWT is NP-hard. (Reduction from 3-SAT.) 87