Toward NP-Completeness: IntroductionAlmost 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 nopolynomial-time algorithm is known. We strongly suspect that many problems cannot be solved efficiently.Toward NP-Completeness: IntroductionIn the last few weeks, we have been dealing with several “hard” problems, like:– Graph k-coloring: Knpossible color assignments– Knapsack problem– Graph Hamilton Circuit– Bin-Packing(recall knapsack)– Euclidean TSP(Traveling Salesman Problem)Toward NP-Completeness: SATSatisfiability(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, 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 satisfiableif there exists an assignment of 0s and 1s to its variables such that the value of the expression is 1. )()()( zyxzyxzyxS ++•++•++=Toward NP-Completeness: SAT• Example: • 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). 2ndifferent truth assignments.)()()()()( zyxyzzxyxzyx ++•+•+•+•++At least one is trueAll three the sameAt least one is falseToward 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 language-recognition 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 L1and L2be two languages from the input spaces U1and U2. We say that L1is Polynomially reducible to L2∃ a polynomial-time algorithm that converts each inputs u1∈U1to another input u2∈ U2such that u1∈L1iff 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 U1and U2, so, in particular, the size of u2is also polynomial in the size of u1.Toward NP-Completeness: Preliminary• Theorem: If L1polynomially reducible to L2and ∃polynomial-time algorithm for L2, then ∃ a polynomial-time algorithm for L1. ( Denoted as L1αL2.)• Corollary 1: L1αL2, and L2αL3L1αL3• Corollary 2: L1αL2, and L2αL1polynomially equivalent.Note that: • Problems we mentioned above are “non-solvable”.(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 , 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: – Z: # Distinct_Factors?Claim: YXPT≤XYPT≤XZPT≤Toward NP-Completeness: Definitions and ClassificationsClass of Decision Problems:• P: Problems could be solved by deterministic algorithm in polynomial time.• NP: Problems for which ∃ a non-deterministicalgorithm 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 NP-complete problem if:1) X belongs to NP, and2) 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 ProofThe 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 ≤kvertices?• CLIQUE: Does G contain a clique of size ≥k?NP-Completeness ProofqA 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: ReductionVertex CoverClique 3SATSAT3-ColorabilityDominating SetAll NP problems4 3125NP-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( , n-k), where n = |V|.– Observe: