Question? Leave a message!




The "first" NP-complete problem

The "first" NP-complete problem
Dr.AlexanderTyler Profile Pic
Dr.AlexanderTyler,India,Teacher
Published Date:21-07-2017
Website URL
Comment
8. INTRACTABILITY II P vs. NP ‣ NP-complete ‣ co-NP ‣ NP-hard ‣ Lecture slides by Kevin Wayne
 Copyright © 2005 Pearson-Addison Wesley
 http://www.cs.princeton.edu/wayne/kleinberg-tardos Last updated on 1/31/17 6:57 AMRecap 3-SAT 
 INDEPENDENT-SET DIR-HAM-CYCLE GRAPH-3-COLOR SUBSET-SUM VERTEX-COVER SCHEDULING HAM-CYCLE PLANAR-3-COLOR SET-COVER TSP 3-SAT poly-time reduces to all of these problems (and many, many more) 2 3-SAT poly-time reduces to INDEPENDENT-SET8. INTRACTABILITY II P vs. NP ‣ NP-complete ‣ co-NP ‣ NP-hard ‣Decision problems Decision problem. Problem X is a set of strings. Instance s is one string. Algorithm A solves problem X: A(s) = yes iff s ∈ X. 
 Def. Algorithm A runs in polynomial time if for every string s, A(s) terminates in at most p( s ) "steps", where p(⋅) is some polynomial function. 
 length of s 
 
 Ex. Problem PRIMES = 2, 3, 5, 7, 11, 13, 17, 23, 29, 31, 37, …. . Instance s = 592335744548702854681. 8 AKS algorithm: solves PRIMES in O( s ) steps. 4Definition of P P. Decision problems for which there is a poly-time algorithm. Problem Description Algorithm yes no grade-school 51, 17 51, 16 MULTIPLE Is x a multiple of y ? division Euclid (300 BCE) 34, 39 34, 51 REL-PRIME Are x and y relatively prime ? AKS (2002) 53 51 PRIMES Is x prime ? Is the edit distance between dynamic niether acgggt EDIT-DISTANCE neither ttttta programming x and y less than 5 ? & & " % " % 0 1 1 4 1 0 0 1 Gauss-Edmonds Is there a vector x that % ( % ( ' ' 2 4 −2 , 2 1 1 1 , 1 L-SOLVE % ( % ( ' ' elimination satisfies Ax = b ? % ( % ( ' ' 0 3 15 36 0 1 1 1 ' ' & & Is an undirected graph
 depth-first search € € U-CONN G connected? (Theseus) 5NP Certification algorithm intuition. Certifier views things from "managerial" viewpoint. Certifier doesn't determine whether s ∈ X on its own;
 rather, it checks a proposed proof t that s ∈ X. 
 Def. Algorithm C(s, t) is a certifier for problem X if for every string s,
 s ∈ X iff there exists a string t such that C(s, t) = yes. 
 "certificate" or "witness" 
 Def. NP is the set of problems for which there exists a poly-time certifier. C(s, t) is a poly-time algorithm. Certificate t is of polynomial size: t ≤ p( s ) for some polynomial p(⋅). 
 
 Remark. NP stands for nondeterministic polynomial time. 6Certifiers and certificates: composite COMPOSITES. Given an integer s, is s composite? 
 Certificate. A nontrivial factor t of s. Such a certificate exists iff s is composite. Moreover t ≤ s . 
 Certifier. Check that 1 t s and that s is a multiple of t. 
 
 
 instance s 437669 
 437,669 = 541 × 809 certificate t 541 or 809 
 
 
 
 in fact, COMPOSITES ∈ P Conclusion. COMPOSITES ∈ NP. 7Certifiers and certificates: satisfiability SAT. Given a CNF formula Φ, does it have a satisfying truth assignment? 3-SAT. SAT where each clause contains exactly 3 literals. 
 Certificate. An assignment of truth values to the Boolean variables. 
 Certifier. Check that each clause in Φ has at least one true literal. 
 
 
 instance s Φ = x ∨ x ∨ x ∧ x ∨ x ∨ x ∧ x ∨ x ∨ x 
 ( ) ( ) ( ) 1 2 3 1 2 3 1 2 4 
 certificate t x = true, x = true, x = false, x = false 1 2 3 4 
 € 
 
 
 
 Conclusions. SAT ∈ NP, 3-SAT ∈ NP. 8Certifiers and certificates: Hamilton path HAM-PATH. Given an undirected graph G = (V, E), does there exist a simple path P that visits every node? 
 Certificate. A permutation of the n nodes. 
 Certifier. Check that the permutation contains each node in V exactly once, and that there is an edge between each pair of adjacent nodes. 
 
 
 
 
 
 
 certificate t instance s 
 Conclusion. HAM-PATH ∈ NP. 9Definition of NP NP. Decision problems for which there is a poly-time certifier. Problem Description Algorithm yes no & & " % " % 0 1 1 4 1 0 0 1 Gauss–Edmonds Is there a vector x
 % ( % ( ' ' 2 4 −2 , 2 1 1 1 , 1 L-SOLVE % ( % ( ' ' elimination that satisfies Ax = b ? % ( % ( ' ' 0 3 15 36 0 1 1 1 ' ' & & € € COMPOSITES AKS (2002) 51 53 Is x composite ? Does x have a nontrivial factor FACTOR (56159, 50) (55687, 50) ? less than y ? ¬ x ∨ ¬ x ∨ ¬ x ¬ x ∨ ¬ x 1 2 3 1 2 Given a CNF formula, does it have SAT ? ¬ x ∨ ¬ x ∨ ¬ x ¬ x ∨ ¬ x 1 2 3 1 2 a satisfying truth assignment? ¬ x ∨ ¬ x ∨ ¬ x ¬ x ∨ ¬ x 1 2 3 1 2 Can the nodes of a graph G
 3-COLOR ? be colored with 3 colors? Is there a simple path between
 HAM-PATH ? u and v that visits every node? 10Definition of NP NP. Decision problems for which there is a poly-time certifier. “ NP captures vast domains of computational, scientific, and mathematical
 endeavors, and seems to roughly delimit what mathematicians and scientists
 have been aspiring to compute feasibly. ” — Christos Papadimitriou “ In an ideal world it would be renamed P vs VP. ” — Clyde Kruskal 11P, NP, and EXP P. Decision problems for which there is a poly-time algorithm. NP. Decision problems for which there is a poly-time certifier. EXP. Decision problems for which there is an exponential-time algorithm. 
 Claim. P ⊆ NP. Pf. Consider any problem X ∈ P. By definition, there exists a poly-time algorithm A(s) that solves X. Certificate t = ε, certifier C(s, t) = A(s). ▪ 
 Claim. NP ⊆ EXP. Pf. Consider any problem X ∈ NP. By definition, there exists a poly-time certifier C(s, t) for X,
 where certificate t satisfies t ≤ p( s ) for some polynomial p(⋅). To solve input s, run C(s, t) on all strings t with t ≤ p( s ). Return yes if C(s, t) returns yes for any of these potential certificates. ▪ 
 Remark. Time-hierarchy theorem implies P ⊊ EXP. 12The main question: P vs. NP Q. How to solve an instance of 3-SAT with n variables? n A. Exhaustive search: try all 2 truth assignments. 
 Q. Can we do anything substantially more clever? Conjecture. No poly-time algorithm for 3-SAT. "intractable" 13The main question: P vs. NP Does P = NP? Cook 1971, Edmonds, Levin, Yablonski, Gödel
 Is the decision problem as easy as the certification problem? 
 
 
 NP EXP EXP 
 P 
 P = NP 
 
 
 If P ≠ NP If P = NP 
 
 If yes. Efficient algorithms for 3-SAT, TSP, 3-COLOR, FACTOR, … If no. No efficient algorithms possible for 3-SAT, TSP, 3-COLOR, … 
 Consensus opinion. Probably no. 14Possible outcomes P ≠ NP. “ I conjecture that there is no good algorithm for the traveling salesman problem. My reasons are the same as for any mathematical conjecture: (i) It is a legitimate mathematical possibility and (ii) I do not know.” — Jack Edmonds 1966 15Possible outcomes P ≠ NP. “ In my view, there is no way to even make intelligent guesses about the answer to any of these questions. If I had to bet now, I would bet that P is not equal to NP. I estimate the half-life of this problem at 25–50 more years, but I wouldn’t bet on it being solved before 2100. ” — Bob Tarjan (2002) “ We seem to be missing even the most basic understanding of the nature of its difficulty…. All approaches tried so far probably (in
 some cases, provably) have failed. In this sense P =NP is different from many other major mathematical problems on which a gradual progress was being constantly done (sometimes for centuries) whereupon they yielded, either completely or partially. ” — Alexander Razborov (2002) 16Possible outcomes P = NP. “ I think that in this respect I am on the loony fringe of the mathematical community: I think (not too strongly) that P=NP and this will be proved within twenty years. Some years ago, Charles Read and I worked on it quite bit, and we even had a celebratory dinner in a good restaurant before we found an absolutely fatal mistake. ”
 — Béla Bollobás (2002) 17Other possible outcomes 100 P = NP, but only Ω(n ) algorithm for 3-SAT. 
 logn P ≠ NP, but with O(n ) algorithm for 3-SAT. 
 P = NP is independent (of ZFC axiomatic set theory). “ It will be solved by either 2048 or 4096. I am currently somewhat pessimistic. The outcome will be the truly worst case scenario: namely that someone will prove “P = NP because there are only finitely many obstructions to the opposite hypothesis”; hence there exists a polynomial time solution to SAT but we will never know
 its complexity ” — Donald Knuth 18Millennium prize Millennium prize. 1 million for resolution of P = NP problem. 19Looking for a job? Some writers for the Simpsons and Futurama. J. Steward Burns. M.S. in mathematics (Berkeley '93). David X. Cohen. M.S. in computer science (Berkeley '92). Al Jean. B.S. in mathematics. (Harvard '81). Ken Keeler. Ph.D. in applied mathematics (Harvard '90). Jeff Westbrook. Ph.D. in computer science (Princeton '89). Copyright © 1990, Matt Groening Copyright © 2000, Twentieth Century Fox 20