CSE332: Data AbstractionsLecture 27: A Few Words on NPTyler RobisonSummer 20101Easily one of the most important questions in Computer Science:2Does P=NP? Of course, we need to go into what these terms mean P and NP are classes of problems P: Class of problems that can be solved in polynomial time NP: Class of problems where an answer can be verified in polynomial time We‟ll get into what that means The question is, are these sets equivalent? A question that computer scientists & mathematicians have been grappling with for a long time Most believe that P!=NP, but no one‟s proven it One such proof recently in the news (P!=NP; probably not valid)Wow, that’s fantastic… who cares?3 P=NP would mean that many „difficult‟ problems that could previously only be solved in exponential time could now be solved in polynomial time Some algorithms (such as cryptography) are based around the „difficulty‟ of brute-forcing it, but the ease of which an answer can be verified You can break many online encryptions now… with enough computing power Say, an enormous # of computers Or one computer running for several centuries And you don‟t break the scheme itself; you break it for a single session If P=NP, much of existing cryptography would (in theory) be insecureWhy, cont.4 Proving equivalence (or non equivalence) of two problem classes interesting mathematically Proving (or disproving) P = NP is among the most vexing and important open questions in computer science and probably mathematics A $1M prize, the Turing Award, and eternal fame await Sort of the “Fermat‟s Last Theorem” of the CS world (except, this is unsolved)Topic doesn’t really belong in CSE3325 This lecture mentions some highlights of NP, the P vs. NP question, and NP-completeness It should not be part of CSE332: We don‟t spend enough time to do it justice To really cover it, a much larger block of time is needed, and after relevant theory background It‟s not on the final But you are all (?) “in transition” Due to recent shifting around of CS curriculum Encourage you to take Algorithms or Theory to learn more Remember the Dijsktra‟s quote : “computer science is no more about computers than astronomy is about telescopes” – they are quite relevant here Anyway, next academic year, this lecture drops out of CSE332 And, it‟s an interesting (& important) problemP6 P: The class of problems that can be solved by algorithms running in polynomial time; O(nk) for some constant k Note: For purposes of this discussion, consider logn, nlogn, etc. as roughly the same as polynomial: nlogn < n2, so it‟s „about that fast‟ Contrast with exponential time: very, very slow Every problem we have studied is in P Examples: Sorting, minimum spanning tree, … Yet many problems don‟t have efficient algorithms! While we may have been quite concerned with getting sorting down from O(n2) to O(nlogn), in the grand scheme of things, both are pretty good Really, polynomial time is sufficiently „quick‟ Yes, even something insane like O(n24601) Exponential time is not; very quickly becomes infeasible to solve (precisely, anyway)NP7 NP: The class of problems for which polynomial time algorithms exist to check that an answer is correct Given this potential answer, can you verify that it‟s correct in polynomial time? To solve from scratch, we only know algorithms that can do it in exponential time If P=NP, then that would mean we‟d have polynomial time algorithms for solving NP problems Ex: We saw Dijkstra‟s algorithm for finding shortest path in polynomial time For an unweighted graph, finding the longest path (that doesn‟t repeat vertices) is in NP There is a bit more to it than that; need to modify the problem slightlyMore NP8 We know P  NP That is, if we already know how to solve a problem in polynomial time, we can verify a solution for it in polynomial time too NP stands for “non-deterministic polynomial time” for technical reasons Many details being left out, but this is the gist There are many important problems for which: We know they are in NP (we can verify solutions in polynomial time) We do not know if they are in P (but we highly doubt it) The best algorithms we have to solve them are exponential O(kn) for some constant kNP Example One: Satisfiability9 Input: a logic formula of size m containing n variables Various logical ands, ors, nots, implications, etc. Can assign true or false to each variable, evaluate according to rules, etc. Output: An assignment of Boolean values to the variables in the formula such that the formula is true That is, find an assignment for x1, x2, … xn such that the equation is true; if such an assignment exists A good problem to solve, in that you can use logic to represent many other problems An older branch of AI looked into encoding an agent‟s knowledge this way, then reasoning about the world by evaluating expressionsNP Example One: Satisfiability10 We can solve it via „brute-force‟:  Try every possible variable assignment {x1=true,x2=true,…xn=true}, {x1=false…}… How many possibilities do we need to try? n variables, 2 possible values for each, so 2npossible assignments Not so bad for n=5… looking less bright for n=1,000 So exponential time to solve by checking all possibilities We can verify it quickly though If I give you an assignment {x1=false, x2=….}, you can do it in polynomial time: just evaluate the expression If P=NP, a O(mknk) algorithm to solve this existsNP Example One: Satisfiability11 Quite a few NP problems are like this in that they: Are relatively simple to explain Can be solved easily but slowly by brute-force: simply try all possibilitiesNP Example Two: Subset sum12Input: An array of n numbers and a target-sum sumOutput: A subset of the numbers that add up to sum if one existsO(2n) algorithm: Try every subset of arrayO(nk) algorithm: Unknown, probably does not existVerifying a solution: Given a subset that allegedly adds up to sum, add them up in O(n)14 17 5 2 3 2 6 7 6 1731?NP Example Three: Vertex Cover (modified)13Input: A graph (V,E) and a number mOutput: A subset S of V such that for every edge (u,v) in E, at least one of u or v is in S and |S|=m (if such an S exists)That is, every vertex