Great Theoretical Ideas In Computer Science Anupam Gupta Lecture 29 CS 15 251 Dec 8 2005 Fall 2005 Carnegie Mellon University P vs NP what is efficient computation A Graph Named Gadget NODES or VERTICES EDGES K COLORING We define a k coloring of a graph 1 Each node get colored with one color 2 At most k different colors are used 3 If two nodes have an edge between them then they must have different colors A graph is called k colorable iff it has a k coloring Sometimes also called proper colorings A 2 CRAYOLA Question Is Gadget 2 colorable A 2 CRAYOLA Question Is Gadget 2 colorable No it contains a triangle A 3 CRAYOLA Question Is Gadget 3 colorable A 3 CRAYOLA Question Is Gadget 3 colorable A 3 CRAYOLA Question Is Gadget 3 colorable A 3 CRAYOLA Question Is Gadget 3 colorable Yes A 3 CRAYOLA Question A 3 CRAYOLA Question 3 Coloring Is Decidable by brute force Try out all 3n colorings until you determine if G has a 3 coloring Membership in 3COLOR is not undecidable But is it efficient to decide this 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 But we don t know that yet for many common problems 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 Definition We say a language L is in P if there is a program A and a polynomial p such that for any x in A given x as input runs for p x time and answers question is x in L correctly The class P Definition We say function F is in P if there is a program A and a polynomial p such that for any x in A given x as input runs for p x time and A x F x technically called FP but we will blur the distinction for this lecture The class P The set of all languages L that can be recognized in polynomial time The set of functions that can be computed 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 Example 2 2COLOR connected G vertices of G can be 2 colored so that adjacent nodes don t have same color Such colorings are called proper colorings Program A2 Pick a vertex and color it red Repeat if uncolored node has both red and blue neighbors abort if uncolored node has some neighbors red color it blue if uncolored node has some neighbors blue color it red If aborted then G not 2 colorable else have 2 coloring Languages functions in P Example 3 3COLOR G vertices of G can be 3 colored T O N O N K N W Languages functions in P And now a problem for Boolean circuits C Languages functions in P And now a problem dealing with Combinational Circuits AND OR NOT 0 1 gates wired together with no feedback allowed x1 AND x2 AND AND x3 OR OR OR OR CIRCUIT SATISFIABILITY Given a circuit with n inputs and one output is there a way to assign 0 1 values to the input wires so that the output value is 1 true Yes this circuit is satisfiable It has satisfying assignment 110 11 0 AND NOT AND 1 Languages functions in P Example 4 CIRCUIT SATISFIABILITY N W Given A circuit with n inputs and one output is there a way to assign 0 1 values to the input wires so that the output value is 1 true T O N O N K Brute force try all 2 n assignments Exponential time Onto the new class NP Recall the class P We say a language L is in P if there is a program A and a polynomial p such that for any x in A given x as input runs for 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 language L is in NP if there is a program A and a polynomial p a short proof such that for any x in that x …
View Full Document
Unlocking...