Algorithm Design by Éva Tardos and Jon Kleinberg • Copyright © 2005 Addison Wesley, Neil Rhodes • Slides by Kevin Wayne, modified by Neil Rhodes8. NP and Computational IntractabilityCSE 101UC San DiegoSpring, 2005Neil Rhodes2Algorithmic Design Patterns and Anti-PatternsAlgorithmic design patterns.! Greed. O(n log n) interval scheduling.! Divide-and-conquer. O(n log n) sorting.! Dynamic programming. O(n2) edit distance.! Network flow. O(n3) bipartite matching.Algorithmic anti-design patterns.! NP-completeness O(nk) algorithm unlikely.! PSPACE-completeness. O(nk) certifying algorithm unlikely.! Undecidability. No algorithm possible.3NPWe’ll look only at decision problems! Problems for which the answer is yes or no! Optimization problem: what is the longest path?! Decision problem: is there a path of size k or larger?NP = Set of problems for which a solution can be verified in polynomialtime! Given a certificate for a solution (certificate is polynomial in theinput size), certifier checks to see whether the solution is correct! For example, a certificate for path of size k or larger is the pathitself– Certifier: check that each edge is in the original graph, checkthat the path has at least k edgesNP problems can be solved in exponential time! Run the certifier on each of the exponential number of certificates4Historical NoteNP stands for Non-deterministic Polynomial time! Alternative definition of NP: guess a certificate (non-deterministically) and then verify it in polynomial time! Our definition doesn’t care where the certificate comes from: justconcentrates on the existence of a polynomial-time certifierP (Polynomial time) = Set of problems for which a solution can be foundin polynomial timeBiggest question in Computer Science: Does P = NP?5NP ProblemsNP-hard: as hard as any problem in NP! But need not be in NP itselfNP-complete (NPC): the hardest of the NP problems! NP-hard and in NP itself! If any NP-complete problem can be solved in polynomial time, allproblems in NP can be solved in polynomial time! Alternatively: if some NP problem can’t be solved in polynomial time,then no NP-complete problem an be solved in polynomial time6Relationship between P and NPP ! NPPossibility 1: P = NP=NPC! Every NP problem can be solved in polynomial timePossibility 2: P ! NP! No NP-complete problem can be solved in polynomial time! Believed by many to be trueAlgorithm Design by Éva Tardos and Jon Kleinberg • Copyright © 2005 Addison Wesley, Neil Rhodes • Slides by Kevin Wayne, modified by Neil Rhodes8.1. Polynomial-Time Reductions8Classify Problems According to Computational RequirementsQ. Which problems will we be able to solve in practice?A working definition. [Cobham 1960, Edmonds, 1962] Those withpolynomial-time algorithms.Yes Probably NoShortest path Longest pathEuler cycle Hamiltonian cycleMin cut Max cut2-SAT 3-SATMatching 3D-matchingPrimality testing FactoringPlanar 4-color Planar 3-colorBipartite vertex cover Vertex cover9Classify ProblemsDesiderata. Classify problems according to those that can be solved inpolynomial-time and those that cannot.Provably requires exponential-time.! Given a Turing machine, does it halt in at most k steps?! Given a board position in an n-by-n generalization of chess, can blackguarantee a win?Unfortunately… huge number of fundamental problems have defiedclassification for decades.Fortunately… they were shown to be "computationally equivalent" andintractable for all practical purposes.10Polynomial-Time ReductionDesiderata'. Suppose we could solve X in polynomial-time. What elsecould we solve in polynomial time?Reduction. Problem X polynomial reduces 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.Remarks.! We pay for time to write down instances sent to black box #instances of Y must be of polynomial size.! Note: Cook reducibility.! Notation: X " P Y.don't confuse with reduces fromcomputational model supplemented by special pieceof hardware that solves instances of Y in a single stepas opposed to Karp reductions11Polynomial-Time ReductionPurpose. Classify problems according to relative difficulty.Design algorithms. If X " P Y and Y can be solved in polynomial-time,then X can be solved in polynomial time.Establish intractability. If X " P Y and X cannot be solved inpolynomial-time, then X cannot be solved in polynomial time.Establish equivalence. If X " P Y and Y " P X, we use notation X $ P Y.up to cost of reduction12Showing a Problem Q is NP-CompleteChoose a known NP-complete problem, PReduce P to Q! P " P Q– Prove reduction is correct– Prove reduction works in polynomial timeProve that Q is in NP13Polynomial-Time ReductionBasic strategies.! Reduction by simple equivalence.! Reduction from special case to general case.! Reduction by encoding with gadgets.14Independent SetINDEPENDENT SET: Given a graph G = (V, E) and an integer k, is there asubset of vertices S ! V such that |S| % k, and for each edge at mostone 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 set15Vertex CoverVERTEX COVER: Given a graph G = (V, E) and an integer k, is there asubset of vertices S ! V such that |S| " k, and for each edge, at leastone 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 cover16Vertex Cover and Independent SetClaim. VERTEX-COVER $P INDEPENDENT-SET.Pf. We show S is an independent set iff V & S is a vertex cover.vertex coverindependent set17Vertex Cover and Independent SetClaim. VERTEX-COVER $P INDEPENDENT-SET.Pf. We show 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.18Polynomial-Time ReductionBasic strategies.! Reduction by simple equivalence.! Reduction from special case to general case.! Reduction by encoding with gadgets.19Set CoverSET COVER: Given a set U of elements, a collection S1, S2, . . . , Sm ofsubsets of U, and an integer k, does there