The Theory of NP-CompletenessThe theory of NP-completenessClassifying problemsIntractable problemsWhy is this classification useful?Slide 6Hard practical problemsHow are they solved?The theory of NP completenessWe will need to discussDecision ProblemsA decision problem: HAMILTONIAN-CYCLEConverting to decision problemsAn optimization problem: traveling salesmanA decision problem for traveling salesman (TS)The relation betweenThe class PThe goal of verification algorithmsVerification AlgorithmsPolynomial bound verification algorithmsThe problem PATHA verification algorithm for PATHExample: A verification algorithm for TSThe class NPThe relation between P and NPSlide 26Polynomial reductionsSlide 28Two simple problemsIs there a transformation?Does it satisfy all the requirements?The other directionSlide 33NP-complete problemsExamples of NP-Complete problemsCoping with NP- Complete ProblemsNP-complete problems: TheoremNP-completeness and ReducibilityThe Satisfiability problemConjunctive Normal Form (CNF)Slide 41Slide 42Slide 43A verification algorithm for SatisfiabilityThe Theory of NP-CompletenessTractable and intractable problemsNP-complete problemsNP 2The theory of NP-completeness•Tractable and intractable problems•NP-complete problemsNP 3Classifying problems•Classify problems as tractable or intractable.•Problem is tractable if there exists at least one polynomial bound algorithm that solves it.•An algorithm is polynomial bound if its worst case growth rate can be bound by a polynomial p(n) in the size n of the problemconstant a is where...)(01kanananpknNP 4Intractable problems•Problem is intractable if it is not tractable.•All algorithms that solve the problem are not polynomial bound. •It has a worst case growth rate f(n) which cannot be bound by a polynomial p(n) in the size n of the problem. •For intractable problems the bounds are:f n c nn n( ) , ,log or etc.NP 5Why is this classification useful?•If problem is intractable, no point in trying to find an efficient algorithm•All algorithms will be too slow for large inputs.NP 6Intractable problems•Turing showed some problems are so hard that no algorithm can solve them (undecidable)•Other researchers showed some decidable problems from automata, mathematical logic, etc. are intractable: Presburger ArithmeticPNPNo problem is knownfor certain to be in hereHalting Problemand Presburger Arith.are in hereNP 7Hard practical problems•There are many practical problems for which no one has yet found a polynomial bound algorithm.•Examples: traveling salesperson, 0/1 knapsack, graph coloring, bin packing etc.•Most design automation problems such as testing and routing. •Many networks, database and graph problems.NP 8How are they solved?•A variety of algorithms based on backtracking, branch and bound, dynamic programming, etc. •None can be shown to be polynomial boundNP 9The theory of NP completeness•The theory of NP-completeness enables showing that these problems are at least as hard as NP-complete problems•Practical implication of knowing problem is NP-complete is that it is probably intractable ( whether it is or not has not been proved yet)•So any algorithm that solves it will probably be very slow for large inputsNP 10We will need to discuss•Decision problems•Converting optimization problems into decision problems•The relationship between an optimization problem and its decision version•The class P•Verification algorithms•The class NP•The concept of polynomial transformations•The class of NP-complete problemsNP 11Decision Problems•A decision problem answers yes or no for a given input•Examples: –Given a graph G Is there a path from s to t of length at most k? –Does graph G contain a Hamiltonian cycle?–Given a graph G is it bipartite?NP 12A decision problem: HAMILTONIAN-CYCLE•A Hamiltonian cycle of a graph G is a cycle that includes each vertex of the graph exactly once.•Problem: Given a graph G, does G have a Hamiltonian cycle?NP 13Converting to decision problems•Optimization problems can be converted to decision problems (typically) by adding a bound B on the value to optimize, and asking the question:–Is there a solution whose value is at most B? (for a minimization problem)–Is there a solution whose value is at least B? (for a maximization problem)NP 14An optimization problem: traveling salesman •Given:–A finite set C={c1,...,cm} of cities, –A distance function d(ci, cj) of nonnegative numbers. •Find the length of the minimum distance tour which includes every city exactly onceNP 15A decision problem for traveling salesman (TS)•Given a finite set C={c1,...,cm} of cities, a distance function d(ci, cj) of nonnegative numbers and a bound B•Is there a tour of all the cities (in which each city is visited exactly once) with total length at most B?• There is no known polynomial bound algorithm for TS.NP 16The relation between•If we have a solution to the optimization problem we can compare the solution to the bound and answer “yes” or “no”.•Therefore if the optimization problem is tractable so is the decision problem•If the decision problem is “hard” the optimization problems are also “hard”–If the optimization was easy then the decision problem is easy.NP 17The class P•P is the class of decision problems that are polynomial bounded•Is the following problem in P?–Given a weighted graph G, is there a spanning tree of weight at most B?•The decision versions of problems such as shortest distance, and minimum spanning tree belong to PNP 18The goal of verification algorithms•The goal of a verification algorithm is to verify a “yes” answer to a decision problem’s input (i.e., if the answer is “yes” the verification algorithm verify this answer)•The inputs to the verification algorithm are:– the original input (problem instance) and– a certificate (possible solution)NP 19Verification Algorithms•A verification algorithm, takes a problem instance x and answers “yes”, if there exists a certificate y such that the answer for x with certificate y is “yes”•Consider HAMILTONIAN-CYCLE•A problem instance x lists the vertices and edges of G: ({1,2,3,4}, {(3,2), (2,4), (3,4), (4,1), (1, 3)}) •There exists a certificate y = (3, 2, 4, 1, 3) for which the verification algorithm answers “yes” 1432NP 20Polynomial bound verification algorithms•Given a decision problem