第13章_NP完全性NP_Complete.ppt

NP-Completeness Graphs NP-Completeness Outline and Reading P and NP (§13.1) NP-completeness (§13.2) Some NP-complete problems (§13.3) Approximation Algorithms for NP-Complete Problems (§13.4) Optional: Backtracking and Branch-and-Bound (§13.4) Running Time Revisited Input size, n To be exact, let n denote the number of bits in a nonunary encoding of the input All the polynomial-time algorithms studied so far in this course run in polynomial time using this definition of input size. Exception: any pseudo-polynomial time algorithm Dealing with Hard Problems What to do when we find a problem that looks hard… Dealing with Hard Problems Sometimes we can prove a strong lower bound… (but not usually) Dealing with Hard Problems NP-completeness let’s us show collectively that a problem is hard. Polynomial-Time Decision Problems To simplify the notion of “hardness,” we will focus on the following: Polynomial-time as the cut-off for efficiency Decision problems: output is 1 or 0 (“yes” or “no”) Examples: Does a given graph G have an Euler tour? Does a text T contain a pattern P? Does an instance of 0/1 Knapsack have a solution with benefit at least K? Does a graph G have an MST with weight at most K? Problems and Languages A language L is a set of strings defined over some alphabet Σ Every decision algorithm A defines a language L L is the set consisting of every string x such that A outputs “yes” on input x. We say “A accepts x’’ in this case Example: If A determines whether or not a given graph G has an Euler tour, then the language L for A is all graphs with Euler tours. The Complexity Class P A complexity class is a collection of languages P is the complexity class consisting of all languages that are accepted by polynomial-time algorithms For each language L in P there is a polynomial-time decision algorithm A for L. If n=|x|, for x in L, then A runs in p(n) time on input x. The function p(n) is some polynomial The Complexity Class NP We say that an algorithm is non-de