Algorithm Design by Éva Tardos and Jon Kleinberg • Copyright © 2005 Addison Wesley • Slides by Kevin Wayne8.2 Definition of NP2Decision ProblemsDecision problem.! X is a set of strings.! Instance: string s.! Algorithm A solves problem X: A(s) = yes iff s ! X.Polynomial time. Algorithm A runs in poly-time if for every string s,A(s) terminates in at most p(|s|) "steps", where p(") is some polynomial.PRIMES: X = { 2, 3, 5, 7, 11, 13, 17, 23, 29, 31, 37, …. }Algorithm. [Agrawal-Kayal-Saxena, 2002] p(|s|) = |s|8.length of s3Definition of PP. Decision problems for which there is a poly-time algorithm.51, 1651, 17Grade schooldivisionIs x a multiple of y?MULTIPLE34, 5134, 39Euclid (300 BCE)Are x and y relatively prime?RELPRIME5153AKS (2002)Is x prime?PRIMESacgggttttttanietherneitherDynamicprogrammingIs the edit distance betweenx and y less than 5?EDIT-DISTANCEIs there a vector x thatsatisfies Ax = b?DescriptionGauss-EdmondseliminationAlgorithmLSOLVEProblem NoYes! 0 1 12 4 "20 3 15# $ % % % & ' ( ( ( , 4236# $ % % % & ' ( ( ( ! 1 0 01 1 10 1 1" # $ $ $ % & ' ' ' , 111" # $ $ $ % & ' ' ' 4NPCertification 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.NP. Decision problems for which there exists a poly-time certifier.Remark. NP stands for nondeterministic polynomial-time.C(s, t) is a poly-time algorithm and|t| # p(|s|) for some polynomial p(")."certificate" or "witness"5Certifiers and Certificates: CompositeCOMPOSITES. Given an integer s, is s composite?Certificate. A nontrivial factor t of s. Note that such a certificateexists iff s is composite. Moreover |t| # |s|.Certifier.Instance. s = 437,669.Certificate. t = 541 or 809.Conclusion. COMPOSITES is in NP.437,669 = 541 $ 809boolean C(s, t) { if (t # 1 or t % s) return false else if (s is a multiple of t) return true else return false}6Certifiers and Certificates: 3-SatisfiabilitySAT. Given a CNF formula &, is there a satisfying assignment?Certificate. An assignment of truth values to the n boolean variables.Certifier. Check that each clause in & has at least one true literal.Ex.Conclusion. SAT is in NP.! x1" x2" x3( )# x1" x2" x3( )# x1" x2" x4( ) # x1 " x3 " x4( )! x1= 1, x2= 1, x3= 0, x4= 1instance scertificate t7Certifiers and Certificates: Hamiltonian CycleHAM-CYCLE. Given an undirected graph G = (V, E), does there exist asimple cycle C that visits every node?Certificate. A permutation of the n nodes.Certifier. Check that the permutation contains each node in V exactlyonce, and that there is an edge between each pair of adjacent nodes inthe permutation.Conclusion. HAM-CYCLE is in NP.instance s certificate t8P, NP, EXPP. Decision problems for which there is a poly-time algorithm.EXP. Decision problems for which there is an exponential-time algorithm.NP. Decision problems for which there is a poly-time certifier.Claim. P ' NP.Pf. Consider any problem X in 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 in NP.! By definition, there exists a poly-time certifier C(s, t) for X.! 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. !9The Main QuestionDoes P = NP? [Cook, 1971]! Is the decision problem as easy as the certification problem?! Clay $1 million prize.If yes: Efficient algorithms for 3-COLOR, TSP, FACTOR, SAT, …If no: No efficient algorithms possible for 3-COLOR, TSP, SAT, …Consensus opinion on P = NP? Probably no.EXPNPPIf P ) NPIf P = NPEXPP = NPwould break RSA cryptography(and potentially collapse economy)10The Simpson's: P = NP?Copyright © 1990, Matt Groening11Futurama: P = NP?Copyright © 2000, Twentieth Century Fox12Looking for a Job?Some writers for the Simpsons and Futurama.! J. Steward Burns. M.S. in mathematics, Berkeley, 1993.! David X. Cohen. M.S. in computer science, Berkeley, 1992.! Al Jean. B.S. in mathematics, Harvard, 1981.! Ken Keeler. Ph.D. in applied mathematics, Harvard, 1990.! Jeff Westbrook. Ph.D. in computer science, Princeton, 1989.Algorithm Design by Éva Tardos and Jon Kleinberg • Copyright © 2005 Addison Wesley • Slides by Kevin Wayne8.3 NP-Complete14Polynomial TransformationDef. Problem X polynomial reduces (Cook) to problem Y if arbitraryinstances of problem X can be solved using:! Polynomial number of standard computational steps, plus! Polynomial number of calls to oracle that solves problem Y.Def. Problem X polynomial transforms (Karp) to problem Y if given anyinput x to X, we can construct an input y such that x is a yes instanceof X iff y is a yes instance of Y.Note. Polynomial transformation is polynomial reduction with just onecall to oracle for Y, exactly at the end of the algorithm for X. Almostall previous reductions were of this form.Open question. Are these two concepts the same?we require |y| to be of size polynomial in |x|we abuse notation # p and blur distinction15NP-CompleteNP-complete. A problem Y in NP with the property that for everyproblem X in NP, X # p Y.Theorem. Suppose Y is an NP-complete problem. Then Y is solvable inpoly-time iff P = NP.Pf. * If P = NP then Y can be solved in poly-time since Y is in NP.Pf. + Suppose Y can be solved in poly-time.! Let X be any problem in NP. Since X # p Y, we can solve X inpoly-time. This implies NP ' P.! We already know P ' NP. Thus P = NP. !Fundamental question. Do there exist "natural" NP-complete problems?16,¬, -,-1 0 ? ? ?outputinputshard-coded inputsyes: 1 0 1Circuit SatisfiabilityCIRCUIT-SAT. Given a combinational circuit built out of AND, OR, and NOTgates, is there a way to set the circuit inputs so that the output is 1?17sketchy part of proof; fixing the number of bits is important,and reflects basic distinction between algorithms and circuitsThe "First" NP-Complete ProblemTheorem. CIRCUIT-SAT is NP-complete. [Cook 1971, Levin 1973]Pf. (sketch)! Any algorithm that takes a fixed number of bits n as input andproduces a yes/no answer can be represented by such a circuit.Moreover, if algorithm takes poly-time, then circuit is of poly-size.! Consider some problem X in NP. It has a