15 251 Some Great Theoretical Ideas in Computer Science for Complexity Theory The P vs NP question Lecture 27 April 23 2009 The 1M Questions 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 solved Riemann Hypothesis Yang Mills Theory The P versus NP problem Is perhaps the biggest open problem in computer science and mathematics today Even featured in the TV show NUMB3RS But what is the P NP problem Sudoku 3x3x3 Sudoku 3x3x3 Sudoku 4x4x4 Sudoku 4x4x4 Sudoku Suppose it takes you S n to solve n x n x n V n time to verify the solution Fact V n O n2 x n2 nxnxn Question is there some constant c such that S n nc P vs NP problem nxnxn Does there exist an algorithm for n x n x n Sudoku that runs in time p n for some polynomial p The P versus NP problem informally Is proving a theorem much more difficult than checking the proof of a theorem Let s start at the beginning Hamilton Cycle Given a graph G V E a cycle that visits all the nodes exactly once The Problem HAM Input Graph G V E Output YES if G has a Hamilton cycle NO if G has no Hamilton cycle The Set HAM HAM graph G G has a Hamilton cycle Circuit Satisfiability Input A circuit C with one output Output YES if C is satisfiable NO if C is not satisfiable AND NOT AND The Set SAT SAT all satisfiable circuits C Bipartite Matching Input A bipartite graph G U V E Output YES if G has a perfect matching NO if G does not The Set BI MATCH BI MATCH all bipartite graphs that have a perfect matching Sudoku Input n x n x n sudoku instance Output YES if this sudoku has a solution NO if it does not The Set SUDOKU SUDOKU All solvable sudoku instances Decision Versus Search Problems Decision Problem Search Problem YES NO answers Does G have a Hamilton cycle Can G be 3 colored Find a Hamilton cycle in G if one exists else return NO Find a 3 coloring of G if one exists else return NO Reducing Search to Decision Given an algorithm for decision Sudoku devise an algorithm to find a solution Idea Fill in one by one and use decision algorithm Reducing Search to Decision Given an algorithm for decision HAM devise an algorithm to find a solution Idea Find the edges of the cycle one by one Decision Search Problems We ll study decision problems because they are almost the same asymptotically as their search counterparts Polynomial Time and The Class P of Decision Problems What is an efficient algorithm Is an O n algorithm efficient How about O n log n polynomial time O n2 O nc for some constant c O n10 O nlog n n O 2 O n non polynomial time Does an algorithm running 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 for 3 coloring SAT Sudoku 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 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 sets What if we want to work with graphs or boolean formulas 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 HAM SUDOKU SAT are not known to be in P CO HAM G G does NOT have a Hamilton cycle CO HAM P if and only if HAM P Onto the new class NP Verifying Membership Is there a short proof I can give you for G HAM G BI MATCH C SAT G CO HAM NP A set L NP if there exists an algorithm A and a polynomial p For all x L For all x L there exists y with y p x For all y with y p x such that A x y YES we have A x y NO in p x time in p x time 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 x runs for at most p x time and answers question is x in L correctly can think of A as proving that x is in L NP A set L NP if there exists an algorithm A and a polynomial p For all x L For all x L there exists a y with y p x For all y with y p x such that A x y YES Such that A x y NO in p x time in p x time The Class NP The class of sets L for which there exist short proofs of membership of polynomial length that can be 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 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 G HAM G BI MATCH G SAT G CO HAM 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 Why Care 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 OK OK I care But where do I begin if I want to reason about the P NP problem 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 a long time Also what if I forgot one of …
View Full Document
Unlocking...