Toward NP Completeness Introduction Almost all the algorithms we studies so far were bounded by some polynomial in the size of the input so we call them efficient algorithms However there are many problems for which no polynomial time algorithm is known We strongly suspect that many problems cannot be solved efficiently Toward NP Completeness Introduction In the last few weeks we have been dealing with several hard problems like Graph k coloring Kn possible color assignments Knapsack problem Graph Hamilton Circuit Bin Packing recall knapsack Euclidean TSP Traveling Salesman Problem Toward NP Completeness SAT Satisfiability SAT problem Conjunctive normal form CNF Let S be a Boolean expression in CNF That is S is the product and of several sums or For example S x y z x y z x y z where addition and multiplication correspond to the and and or Boolean operations and each variable is either 0 false or 1 true A Boolean expression is said to be satisfiable if there exists an assignment of 0s and 1s to its variables such that the value of the expression is 1 Toward NP Completeness SAT Example x y z x y x z z y x y z At least one is true All three the same At least one is false Can x y z be set so that this expression is true NO in the above case The SAT problem is to determine whether a given expression is satisfiable without necessarily finding a satisfying assignment 2n different truth assignments Toward NP Completeness Preliminary Decision problem problems with answer either yes or no e g Is there any TSP tour on graph G has length k Decision problem can be viewed as languagerecognition problem e g Is G k TSP U the set of possible inputs to the decision problem L U is the set of inputs which yield yes L the language corresponding to the problem Toward NP Completeness Preliminary Definition Let L1 and L2 be two languages from the input spaces U1 and U2 We say that L1 is Polynomially reducible to L2 a polynomial time algorithm that converts each inputs u1 U1 to another input u2 U 2 such that u1 L1 iff u2 U2 Note The algorithm is polynomial in the size of the input u1 We assume that the notion of size is well defined in the input spaces U1 and U2 so in particular the size of u2 is also polynomial in the size of u1 Toward NP Completeness Preliminary Theorem If L1 polynomially reducible to L2 and polynomial time algorithm for L2 then a polynomial time algorithm for L1 Denoted as L1 L2 Corollary 1 L1 L2 and L2 L3 L1 L3 Corollary 2 L1 L2 and L2 L1 polynomially equivalent Note that Problems we mentioned above are nonsolvable Roughly speaking solvable means a polynomial time algorithm They are equivalent solve one solve all Toward NP Completeness Preliminary Definition X is poly time reducible to Y in sense of Turing written X TP Y if there exists an algorithm for solving X that would be polynomial if we took no account of the time needed to solve arbitrary instances of Y Example X Smallest Factor 2 Y Prime Claim Y TP X Z Distinct Factors P Claim Z T X Toward NP Completeness Definitions and Classifications Class of Decision Problems P Problems could be solved by deterministic algorithm in polynomial time NP Problems for which a non deterministic algorithm whose running time is a polynomial in the size of the input small solutions in poly size like certificate Solution could be easily checked in poly time Non deterministic poly time algorithm Note Whether P NP is not known but most people believe P NP Toward NP Completeness Definitions and Classifications NP Hard A problem X is called an NP hard problem if every problems in NP is polynomially reducible to X NP Complete A problem X is called an NPcomplete problem if 1 X belongs to NP and 2 X is NP hard Also X is NP complete if X NP and Y is polynomially reducible to X for some Y that is NP complete NP Complete problems are the hardest problems in NP Toward NP Completeness Cook s theorem The SAT problem is NP complete Once we have found an NP complete problem proving that other problems are also NP complete becomes easier Given a new problem Y it is sufficient to prove that Cook s problem or any other NP complete problems is polynomially reducible to Y NP Completeness Proof The following five problems are NP complete vertex cover VC dominating set DS 3SAT 3 coloring and clique Definition qA vertex cover of G V E is V V such that every edge in E is incident to some v V Vertex Cover VC Given undirected G V E and integer k does G have a vertex cover with k vertices CLIQUE Does G contain a clique of size k NP Completeness Proof qA dominating set D of G V E is D V such that every v V is either in D or adjacent to at least one vertex of D DS given G k does G have a dominating set of size k 3SAT Give a Boolean expression in DNF such that each clause has exactly 3 variables determine satisfiability NP Completeness Proof Reduction To prove NP completeness of a new problem we must first prove that the problem belongs to NP which is usually but not always easy then reduce a known NP complete problem to our problem in polynomial time The reduction order used for the five problems mentioned above is illustrated in the figure below To make them easier to understand we present the proofs in order of difficulty rather than the tree order This order is indicated in the figure by the numbers of the edges NP Completeness Proof Reduction All NP problems SAT Clique 4 1 Vertex Cover 2 Dominating Set 3 3SAT 5 3 Colorability NP Completeness Proof Vertex Cover VC Problem Given undirected G V E and integer k does G have a vertex cover with k vertices Theorem the VC problem is NP complete Proof Reduction from CLIQUE i e given CLIQUE is NP complete VC is NP This is trivial since we can guess a cover of size k and check it easily in poly time Goal Transform arbitrary CLIQUE instance into VC instance such that CLIQUE answer is yes iff VC answer is yes NP Completeness Proof Vertex Cover VC Claim CLIQUE G k has same answer as VC G n k where n V Observe If C u F clique in G then v u is VC in G NP Completeness Proof Vertex Cover VC Observe If D is a VC in G then G has no edge between vertices in V D So we have k clique in G n k VC in G Can transform in polynomial time NP Completeness Proof DS qDefinition A dominating set D of G V E is D V such that every v V is either in D or adjacent to at least one vertex of D …