Great Theoretical Ideas In Computer Science Anupam Gupta Lecture 28 CS 15 251 Dec 7th 2006 Fall 2006 Carnegie Mellon University Complexity Theory the P vs NP question The 1M question The Clay Mathematics Institute Millenium Prize Problems 1 2 3 4 5 6 7 Birch and Swinnerton Dyer Conjecture Hodge Conjecture Navier Stokes Equations P vs NP Poincar Conjecture Riemann Hypothesis Yang Mills Theory http www claymath org millennium The P versus NP problem Is 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 theorem much more difficult than checking 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 polynomial time How about O n log n O n2 O n10 O nlog n O 2n O n O 222n O nc for some constant c non polynomial time Does an algorithm running in O n100 time count as efficient We consider nonpolynomial 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 have polynomial 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 The Intrinsic Computational Difficulty of Functions Alan Cobham 1964 not the correct Alan Cobham Paths Trees and Flowers Jack Edmonds 1965 this is indeed Jack Edmonds Paths 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 polynomial The class P 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 time and answers question is x in L correctly The class P The 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 only at languages What if we want to work with graphs or boolean formulas 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 NP Recall the class P 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 time and answers question is x in L correctly can think of A as proving that x in L The new class NP We say a set L is in NP if there is a program A and a polynomial p such that for any x in a short proof that x in L 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 Verifier rejects all fake proofs that can be quickly verified The class NP The 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 languages are in NP P NP For 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 NP Set 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 that can be verified in poly time Fact P NP Question Does NP P The P versus NP problem NP contains lots of problems we don t know to be in P Classroom Scheduling Packing objects into bins Scheduling jobs on machines Finding cheap tours visiting a subset of cities Allocating variables to registers Finding good packet routings in networks Decryption Hence proving P NP would break cryptosystems How can we prove that NP P I would have to show that every set in NP has a polynomial time algorithm How do I do that It may take forever Also what if I forgot one of the sets in NP Relax Bonzo We can describe one problem L in NP such that if this problem L is in P then NP P It is a problem that can capture all other problems in NP Theorem Cook Levin SAT is one language in NP such that if we can show SAT is in P then we have shown NP P SAT is a language in NP that can capture all other languages in …
View Full Document
Unlocking...