Slide 1Slide 2The $1M questionThe P versus NP problemSlide 5Slide 6Slide 7Slide 8Slide 9Slide 10The P versus NP problem (informally)Let’s start at the beginning…Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24What is an efficient algorithm?Slide 26Slide 27Slide 28The Class PSlide 30Slide 31Slide 32Slide 33Onto the new class, NPSlide 35Slide 36Slide 37Slide 38The Class NPSlide 40Slide 41Summary: P versus NPSlide 43Slide 44Slide 45Slide 46Slide 47Slide 48Slide 49Slide 50Slide 51Slide 52Reduction from SAT to 3COLORSlide 54Slide 55Slide 56Slide 57Slide 58Slide 59Slide 60Slide 61Slide 62Slide 63Slide 64Slide 65Slide 66Slide 67COMPSCI 102Introduction to Discrete MathematicsComplexity Theory: The P vs NP questionLecture 26 (December 2, 2009)The $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 TheoryThe 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?Sudoku3x3x3x3Sudoku3x3x3x3Sudoku4x4x4x4Sudoku4x4x4x4Sudokun x n x n x n...Suppose it takes you S(n) to solve n x n x n x nV(n) time to verify the solutionFact: V(n) = O(n2 x n2)Question: is there some constant such thatS(n) [V(n)]constant ?Sudokun x n x n...P vs NP problem=Does there exist an algorithm for n x n x n x n sudoku that runs in time P(n) for some polynomial P(n)?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 CycleGiven a graph G = (V,E), a cycle that visits all the nodes exactly onceThe Problem “HAM”The Set “HAM”Input: Graph G = (V,E)Output: YES if G has a Hamilton cycleNO if G has no Hamilton cycleHAM = { graph G | G has a Hamilton cycle }ANDANDNOTCircuit-SatisfiabilityInput: A circuit C with one outputOutput: YES if C is satisfiableNO if C is not satisfiableThe Set “SAT”SAT = { all satisfiable circuits C }Bipartite MatchingInput: A bipartite graph G = (U,V,E)Output: YES if G has a perfect matchingNO if G does notThe Set “BI-MATCH”BI-MATCH = { all bipartite graphs that have a perfect matching }SudokuInput: n x n x n x n sudoku instanceOutput: YES if this sudoku has a solutionNO if it does notThe Set “SUDOKU”SUDOKU = { All solvable sudoku instances }Decision Versus Search ProblemsDecision ProblemYES/NODoes G have a Hamilton cycle?Search ProblemFind a Hamilton cycle in G if one exists, else return NOReducing Search to DecisionGiven an algorithm for decision Sudoku, devise an algorithm to find a solutionIdea:Fill in one-by-one and use decision algorithmReducing Search to DecisionGiven an algorithm for decision HAM, devise an algorithm to find a solutionIdea:Find the edges of the cycle one by oneDecision/Search ProblemsWe’ll study decision problems because they are almost the same (polynominally) as their search counterpartsPolynomial Time and The Class “P” of Decision ProblemsWhat is an efficient algorithm?polynomial timeO(nc) for some constant cnon-polynomialtimeIs an O(n) algorithm efficient?How about O(n log n)?O(n2) ?O(n10) ?O(nlog n) ?O(2n) ?O(n!) ?Does 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?The 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(x) runs for at most p(|x|) timeand answers question “is x in L?” correctly.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.The Class PWhy 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 node 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 PCO-HAM = { G | G does NOT have a Hamilton cycle}CO-HAM P if and only if HAM POnto the new class, NPVerifying MembershipIs there a short “proof” I can give you for:G HAM?G BI-MATCH?G SAT?G CO-HAM?NPA set L NPif there exists an algorithm A and a polynomial p( )For all x Lthere exists y with |y| p(|x|) such that A(x,y) = YESin p(|x|) timeFor all x LFor all y with |y| p(|x|) in p(|x|) timewe have A(x,y) = NOcan think of A as “proving” that x is in LRecall the 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(x) runs for at most p(|x|) timeand answers question “is x in L?” correctly.NPA set L NPif there exists an algorithm A and a polynomial p( )For all x Lthere exists a y with |y| p(|x|) such that A(x,y) = YESin p(|x|) timeFor all x LFor all y with |y| p(|x|) in p(|x|) timeSuch that A(x,y) = NOThe 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.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?G HAM?G BI-MATCH?G SAT?G CO-HAM?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” that can be verified in poly-time.Fact: P NPQuestion: Does NP P ?Why Care?Classroom SchedulingPacking objects into binsScheduling jobs on machinesFinding cheap tours visiting a subset of citiesAllocating variables to registersFinding good packet routings in networksDecryption…NP Contains Lots of ProblemsWe Don’t Know to be in POK, OK, I care.But Where Do I Begin?How can we prove
View Full Document
Unlocking...