P vs NP: what is efficient computation?A Graph Named “Gadget”NODES or VERTICESEDGESK-COLORINGA 2-CRAYOLA Question!Slide 7A 3-CRAYOLA Question!Slide 9Slide 10Slide 11A 3-CRAYOLA Question.Slide 133-Coloring Is Decidable by brute forceWhat is an efficient algorithm?Slide 16Slide 17Slide 18Slide 19The class P defined in the 50’s.Slide 21Slide 22The class PSlide 24Slide 25Slide 26Slide 27Languages/functions in P?Slide 29Slide 30Slide 31Slide 32Slide 33CIRCUIT-SATISFIABILITYSlide 35Onto the new class, NPRecall the class PThe new class NPThe class NPSlide 40P NPLanguages/functions in NP?Slide 43Summary: P versus NPHamilton CycleNP contains lots of problems we don’t know to be in PThe $1,000,000 questionSlide 48Slide 49The Magic Language: CIRCUITSATSlide 51Slide 52CIRCUIT-SAT and 3COLORSlide 54Slide 55Slide 56Slide 57Slide 58Slide 59Slide 60Slide 61Slide 62You can quickly transform a method to decide 3-coloring into a method to decide circuit satifiability!Slide 64Slide 65Slide 66To show a language L is NP-completeNP-complete problemsReferenceReferencesP vs NP:what is efficient computation?Great Theoretical Ideas In Computer ScienceAnupam GuptaCS 15-251 Fall 2005Lecture 29 Dec 8, 2005 Carnegie Mellon UniversityA Graph Named “Gadget”NODES or VERTICESEDGESK-COLORINGWe define a k-coloring of a graph:1. Each node get colored with one color2. At most k different colors are used3. If two nodes have an edge between them, then they must have different colorsA graph is called k-colorable iff it has a k-coloringSometimes 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.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? A 3-CRAYOLA Question!Yes.A 3-CRAYOLA Question.A 3-CRAYOLA Question.3-Coloring Is Decidable by brute forceTry 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?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!But we don’t know that yet for many common problems…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 PDefinition: 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 PDefinition: 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 lectureThe class PThe 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 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?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}NOT KNOWN!Languages/functions in P?And now a problem for Boolean
View Full Document
Unlocking...