Algorithmic Design Patterns and Anti Patterns 8 NP and Computational Intractability Algorithmic design patterns Greed Divide and conquer Dynamic programming Network flow O n log n interval scheduling O n log n sorting O n2 edit distance O n3 bipartite matching CSE 101 UC San Diego Algorithmic anti design patterns NP completeness O nk algorithm unlikely PSPACE completeness O nk certifying algorithm unlikely Undecidability No algorithm possible Spring 2005 Neil Rhodes Algorithm Design by va Tardos and Jon Kleinberg Copyright 2005 Addison Wesley Neil Rhodes Slides by Kevin Wayne modified by Neil Rhodes 2 NP Historical Note We 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 polynomial time Given a certificate for a solution certificate is polynomial in the input size certifier checks to see whether the solution is correct For example a certificate for path of size k or larger is the path itself Certifier check that each edge is in the original graph check that the path has at least k edges NP problems can be solved in exponential time Run the certifier on each of the exponential number of certificates NP stands for Non deterministic Polynomial time Alternative definition of NP guess a certificate nondeterministically and then verify it in polynomial time Our definition doesn t care where the certificate comes from just concentrates on the existence of a polynomial time certifier P Polynomial time Set of problems for which a solution can be found in polynomial time Biggest question in Computer Science Does P NP 3 4 NP Problems Relationship between P and NP NP hard as hard as any problem in NP But need not be in NP itself NP 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 all problems 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 time P NP Possibility 1 P NP NPC Every NP problem can be solved in polynomial time Possibility 2 P NP No NP complete problem can be solved in polynomial time Believed by many to be true 5 6 Classify Problems According to Computational Requirements 8 1 Polynomial Time Reductions Q Which problems will we be able to solve in practice A working definition Cobham 1960 Edmonds 1962 Those with polynomial time algorithms Algorithm Design by va Tardos and Jon Kleinberg Copyright 2005 Addison Wesley Neil Rhodes Slides by Kevin Wayne modified by Neil Rhodes Yes Probably No Shortest path Longest path Euler cycle Hamiltonian cycle Min cut Max cut 2 SAT 3 SAT Planar 4 color Planar 3 color Bipartite vertex cover Vertex cover Matching 3D matching Primality testing Factoring 8 Classify Problems Polynomial Time Reduction Desiderata Classify problems according to those that can be solved in polynomial time and those that cannot Desiderata Suppose we could solve X in polynomial time What else could we solve in polynomial time 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 black guarantee a win Reduction Problem X polynomial reduces to problem Y if arbitrary instances of problem X can be solved using Polynomial number of standard computational steps plus Polynomial number of calls to oracle that solves problem Y don t confuse with reduces from computational model supplemented by special piece of hardware that solves instances of Y in a single step Unfortunately huge number of fundamental problems have defied classification for decades Remarks We pay for time to write down instances sent to black box instances of Y must be of polynomial size as opposed to Karp reductions Note Cook reducibility Notation X P Y Fortunately they were shown to be computationally equivalent and intractable for all practical purposes 9 10 Polynomial Time Reduction Showing a Problem Q is NP Complete Purpose Classify problems according to relative difficulty Choose a known NP complete problem P Reduce P to Q P P Q Prove reduction is correct Prove reduction works in polynomial time Prove that Q is in NP 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 in polynomial 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 reduction 11 12 Polynomial Time Reduction Independent Set Basic strategies Reduction by simple equivalence Reduction from special case to general case Reduction by encoding with gadgets 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 13 Vertex Cover 14 Vertex Cover and Independent Set Claim VERTEX COVER P INDEPENDENT SET Pf We show S is an independent set iff V S is a 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 independent set vertex cover vertex cover 15 16 Vertex Cover and Independent Set Polynomial Time Reduction Claim VERTEX COVER P INDEPENDENT SET Pf We show S is an independent set iff V S is a vertex cover Basic strategies Reduction by simple equivalence Reduction from special case to general case Reduction by encoding with gadgets 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 17 18 Set Cover Vertex Cover Reduces to Set Cover SET COVER Given a set U of elements a collection S1 S2 Sm of Claim VERTEX COVER P SET COVER these sets whose union is equal to U cover instance whose size equals the size of the vertex cover instance Sample application m available pieces of software Set U of n capabilities that we would like our system to have The ith piece of software provides the set Si