Slide 1The $1M questionThe P versus NP problemSlide 4Slide 5Slide 6Slide 7Slide 8Slide 9The P versus NP problem (informally)Let’s start at the beginning…Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27What is an efficient algorithm?Slide 29Slide 30Slide 31Slide 32The class P defined in the 50’s.Slide 34Slide 35The class PSlide 37Slide 38Slide 39Languages/functions in P?Slide 41Slide 42Onto the new class, NPSlide 44Slide 45Recall the class PThe new class NPThe class NPSlide 49P NPLanguages/functions in NP?Summary: P versus NPSlide 53Slide 54NP contains lots of problems we don’t know to be in PSlide 56Slide 57Slide 58Slide 59Slide 60Slide 61Slide 62Slide 63Slide 64Slide 65Last lecture…Slide 67Slide 68Slide 69Slide 70To show a language L is NP-completeNP-complete problemsReferenceReferencesGreat Theoretical Ideas In Computer ScienceAnupam GuptaCS 15-251 Fall 2006Lecture 28 Dec 7th, 2006 Carnegie Mellon UniversityComplexity Theory: the P vs NP questionThe $1M questionThe Clay Mathematics InstituteMillenium Prize Problems1. Birch and Swinnerton-Dyer Conjecture 2. Hodge Conjecture 3. Navier-Stokes Equations 4. P vs NP 5. Poincaré Conjecture 6. Riemann Hypothesis 7. Yang-Mills Theory http://www.claymath.org/millennium/The P versus NP problemIs perhaps one of the biggest open problems in computer science (and mathematics!) today.(Even featured in the TV show NUMB3RS)But what is the P-NP problem?The P versus NP problem (informally)Is proving a theoremmuch more difficult thanchecking the proof of a theorem?Loosely, that is what the P-vs-NP question asks.Let’s start at the beginning…What is an efficient algorithm?Is an O(n) time algorithm efficient?How about O(n log n)?O(n2) ?O(n10) ?O(nlog n) ?O(2n) ?O(n!) ?O(222n) ?polynomial timeO(nc) for some constant cnon-polynomialtimeDoes an algorithmrunning in O(n100) time count as efficient?We consider non-polynomial time algorithms to be inefficient.And hence a necessary condition for an algorithm to be efficient is that it should run in poly-time.Asking for a poly-time algorithm for a problem sets a (very) low bar when asking for efficient algorithms.The question is: can we achieve even this?I see!Once we know that our favorite problems havepolynomial time algorithms, we can then worry about making them run in O(n log n) or O(n2) time!The class P defined in the 50’s.Paths, Trees and Flowers, Jack Edmonds, 1965. The Intrinsic Computational Difficulty of Functions, Alan Cobham, 1964. not the correct Alan Cobhamthis is indeed Jack EdmondsPaths, Trees and Flowers, Jack Edmonds, 1965. An explanation is due on the use of the words "efficient algorithm"…I am not prepared to set up the machinery necessary to give it formal meaning, nor is the present context appropriate for doing this…For practical purposes the difference between algebraic and exponential order is more crucial than the difference between [computable and not computable]… It would be unfortunate for any rigid criterion to inhibit the practical development of algorithms which are either not known or known not to conform nicely to the criterion… However, if only to motivate the search for good, practical algorithms, it is important to realize that it is mathematically sensible even to question their existence. Edmonds called them “good algorithms”The Intrinsic Computational Difficulty of Functions, Alan Cobham, 1964. For several reasons the class P seems a natural one to consider. For one thing, if we formalize the definition relative to various general classes of computing machines we seem always to end up with the same well-defined class of functions. Thus we can give a mathematical characterization of P having some confidence it characterizes correctly our informally defined class. This class then turns out to have several natural closure properties, being closed in particular under explicit transformation, composition and limited recursion on notation (digit-by-digit recursion). if p( ) and q( ) are polynomials, then p(q( )) is also a polynomialThe class PWe say a set L µ Σ* is in P if there is a program A and a polynomial p() such that for any x in Σ*, A (input x) runs for at most p(|x|) timeand answers question “is x in L?” correctly.The class PThe class of all sets L that can be recognized in polynomial time.The class of all decision problems that can be decided in polynomial time.Why are we looking onlyat languages Σ*?What if we want to work with graphs or booleanformulas?Requiring that L Σ* is not really restrictive, since we can encode graphs and Boolean formulas as strings of 0’s and 1’s.In fact, we do this all the time: inputs for all our programs are just sequences of 0’s and 1’s encoded in some suitable format.Languages/functions in P?Example 1: CONN = {graph G: G is a connected graph}Algorithm A1: If G has n nodes, then run depth first search from any node, and count number of distinct nodes you see. If you see n nodes, G CONN, else not.Time: p1(|x|) = Θ(|x|).Languages/functions in P?Languages/functions in P?Onto the new class, NPRecall the class Pcan think of A as “proving” that x in L.We say a set L µ Σ* is in P if there is a program A and a polynomial p() such that for any x in Σ*, A (input x) runs for at most p(|x|) timeand answers question “is x in L?” correctly.The new class NPWe say a set L µ Σ* is in NP if there is a program A and a polynomial p() such that for any x in Σ*, If x L, there exists a “proof” y with |y| ≤ p(|x|) A(x, y) runs for ≤ p(|x|) time and answers “x is in L” correctly.If x L, for all “proofs” y A(x, y) answers “x not in L” correctly.a short proof that x in Lthat can be quickly “verified”Verifier rejects all “fake” proofsThe class NPThe class of sets L for which there exist “short” proofs of membership (of polynomial length) that can “quickly” verified (in polynomial time).Recall: A doesn’t have to find these proofs y; it just needs to be able to verify that y is a “correct” proof.Which languagesare in NP?P NPFor any L in P, we can just take y to be the empty string and satisfy the requirements.Hence, every language in P is also in NP.Languages/functions in NP?Summary: P versus NPSet L is in P if membership in L can be decided in poly-time.Set L is in NP if each x in L has a short “proof of membership”
View Full Document
Unlocking...