Beyond Computation: The P vs NP Problem - Michael Sipser

well thank you so much for coming here tonight to listen to talk about mathematics I'm Jim Carlson president the clay mathematics Institute which is located on one boh Street right by the Grafton pub or Dunkin Donuts however you wish to located the clay mathematics Institute is dedicated to furthering the creation and dissemination of mathematics it was formed due to the generosity of Landon and Lavinia clay among our many activities are a series of public lectures we generally hold to each year one at Harvard one at MIT the spring public lecture will be at MIT and our speaker will be ingrid daubechies who I think should be viewed as the mother of wavelets which is a branch of mathematics that has had truly astounding applications at the right set of notes here it helps so tonight we're having our lecture here at the mathematics department sponsored by the mathematics department of Harvard University were very very grateful for their hospitality and for this wonderful venue in the Science Center our speaker tonight is Michael SIPP sir he is chair of the mathematics department of MIT which has two branches the Applied Mathematics in the pure mathematics group he will speak on the P versus NP problem I won't say anything about it because Michael can say it much better than I can Michael was an undergraduate at Cornell University he received his PhD at Berkeley and since 1980 he has been at MIT he's taught many courses there including everything from basic calculus to graduate courses in the theory of complexity he's also the author of a widely used textbook introduction to the theory of complexity his research interests are largely in the area of complexity theory but include mathematical logic and common atour --ax so it's a great pleasure to welcome Michael sips or you will speak to us about the P versus NP problem Michael thank you thank you Jim this thing picking up great so thank you all for coming thanks to the Clay Institute for hosting this wonderful series of public lectures in mathematics I think it's a great thing and thanks you know I'm grateful I'm glad to see such a good turnout for a math talk about my favorite topic the P versus NP question so let me tell you first I'm going to jump right in tell you a little bit about that it's a problem in computer science in mathematics and it concerns the amount of time you need to solve various problems on a computer now even though computers very fast for certain kinds of problems they seem to take a long time and it's not really well understood why that is so we're going to explore that let's we'll start off with something simple let's take the problem seven times thirteen that's an example of something we call multiplication just for you know case you're just getting up to speed the answer is 91 and if you look at the reverse problem given the product 91 and you want to try to find the two numbers that multiply together to give that result those are called the factors of 91 you can either do that by remembering the previous slide or you could just start out with the number 91 and figure out what those factors are directly see 7 times 13 give you 91 now let's look at a slightly bigger example now probably this not this is one that you're not going to do in your head and if you're a normal person but if you fed it into a computer you would get the answer out and what's amazing is that the answer would come out in a split second but let's take a look at something more interesting what happens if you look at the reverse problem the factoring problem for that particular product well we already know what the answer is but suppose you didn't write it down from the previous slide you just went directly from this C whoops this product is this product here in blue to the and you wanted to figure out what two factors were okay so that's something you could solve on a computer and actually somebody went ahead went ahead and did that but the difference between this problem and the previous one is that it takes a little longer in fact it was 20 computer years of effort required to solve this problem now you may ask why would somebody care and put in and put all that effort in or for one thing we're mathematicians and you know it's because it's there another reason is somebody paid them 20,000 dollars to do that believe it or not this is true and you may think well why would somebody pay $20,000 to factor a number and you know how can we get a piece of that so well you can I mean here's another number $30,000 in fact no one knows the no one knows the factors of this problem so if you want to turn on your computers and you know want to spend it's going to be more that this is a bigger number this is a bigger number than previous one it's going to be more than 20 computer years probably a lot more but you can earn thirty thousand dollars that way now why in the world is somebody spending that kind of money to factor numbers well this is actually comes from this company called RSA and you can just google it on if you google you know the RSA factoring challenge you will find that you'll find this number the previous number and a whole list of other numbers which are your $50,000 $100,000 $200,000 this is all true and the reason why the RSA company is spending that kind of money to factor numbers is not so much because they're interested in that kind of factorization but they're interested in unjust getting a handle on the progress that people are making in factoring numbers because factoring is essential to their business they're in the business of cryptography designing secret codes for secure communication between computers and the kind of code that they use is called the RSA code is really based on factoring so if so many figures a way of factoring quickly it will break their code that's something they want to know about obviously so that's why RSA is interested in factoring no the question is why is factoring so hard to solve what why does why is factoring takes too long time to solve on a computer well the reason for that is in contrast there's multiplication where you can kind of zoom right down on the answer and factoring all we know how to do is to search for the answer given your number that you want to factor you try dividing by 2 by 3 you can confine yourself just to the prime numbers to save yourself a little bit of time anyway and you tried you know dividing by five seven if at any point you find a number that you find one of those numbers that divide evenly into the number you're trying to factor then you've got a factor and you can stop there but otherwise you just have to keep going on and on and on the number of possible factors that you might have to search through for factorization problems of the sort I just described is absolutely astronomical and that's why it takes even superfast computers a very long time to solve that problem so the process of searching for the answer over a large space of possibilities kind of one by one in a mindless way is we call brute force search and that process is very slow if you have a lot of possibilities that you need to search them now the interesting question here is do you really need to search or is there some way of solving say the factoring problem that zooms in on the answer without searching that would be amazing and in fact we don't know the answer to that question seems like factory needs searching leaf as far as we know I mean you can do some things that are some some improvements on the simple-minded method that I gave you and cut down the search space somewhat but the only out the only procedures that we know still involves searching through a lot of possibilities and we don't know if you can eliminate that or not but let's come to another example here's an example I call the klique problem so given a network here of nodes and lot of nose a little circles and lines which might represent something else say for example the nodes might represent the the members of the math department at MIT okay and we'll draw a line I'll leave off the names we'll do a line connecting to nodes if those two faculty members are friends okay so you can see we have a pretty friendly department more or less and what I'm interested in doing you know sometimes parties now and then and you'd like to invite people over to your home we're all mutual friends one another okay so a group of people who are all connected or group of nodes we're all connected by lines with one another is called a clique so over here we have a three clique it's a four clique four nodes all connected by lines and so on and if what I'm interested in doing is finding among the faculty among these nodes groups which form cliques presumably as large as I can get so I can have a decent sized party so we know over here we've got a three click down here I got a four clique question is is that the best I can do or maybe can I find a bigger clique than that well you're really quick you can see that in fact there is a five-click in this graph here it is maybe a little more clearly and but the point is that if you want to try to find a clique say in a bigger graph is a graph with even more here's a network or graph with even more nodes the number of possibilities say if you want to look for a clique say of eight nodes in here that's not a clique but if you sort of want to try to find one perhaps with eight nodes in it you just have to as far as we know you have to search through all possible subsets of eight nodes to see if any one of them turns out to be a clique and the number of possibilities that you would have to go through to do that is large and in fact if you had instead of just a hundred nodes that I as I've described here if you had hundreds of nodes which is still a pretty modest sized problem and you try to find the biggest clique possible or you know some target size click of a you know of a reasonably decent size it would take centuries maybe even millennia of computer time to search through all the possibilities you see it's a very similar kind of situation with factoring and it's even more similar in that you can ask the same question do you really need to search or is there some way to zoom in on those click on that big click quickly without searching we don't know so both the click and the factoring problem are examples of what I would call needle in the haystack problems you know in case you're not familiar with haystack here's is an example big pile of hay and somewhere in there is the needle and to search for that needle as you can imagine if I take a long time here's a cartoon sort of giving the idea somebody actually found the needle but after searching so it's amazing what you can find on the Internet these days so you know in the case of you know this sort of example of looking for a needle in a haystack here's here's on my model of a haystack if you want to you can ask the problem is searching necessary to find the needle well perhaps you have a magnet then bingo you get the needle right away you don't if you don't have to search at all so the question that we're asking in the case of factoring and click is there some kind of mathematical analog to the magnet that pulls out the answer without having to search for it neither of those cases do we know and in fact that phenomenon is very very pervasive it's very widespread throughout problem and engineering in economics in optimization in in science for example if you looking at problems involving scheduling classes or exams we try to minimize the number of conflicts the only way to do that which finds the best possible answer involves searching through large numbers of schedules or if you want to color a map with a smallest number of colors so that no two adjoining adjacent countries and to put the same color you might have to search through a lot of possible colorings in order to find the one that's the best possible or if you know there's a problem in computational biology where you've given a protein sequence and you're trying to find the configuration that that sequence will fold up into to give you a sense of how of the function with that protein inside the cell we'd be great if we could solve that on a computer but the only way that we know how to do it would involve trying to search through all possible configurations of the protein takes too long this is a real practical problem that people would love to be able to solve it's just beyond our computational ability to solve it by searching and no one knows if there's a you know if there's a faster way another problem of interest to mathematicians is the problem of theorem proving another searching type problem if I want to know is there a proof of a theorem of a certain length so okay you know I'm given some mathematical statements a and I want to know is there a proof which is at most 100 pages well I could do that in principle by a computer I can make that check by computer by searching through every possible proof of 100 pages long and seeing if any one of them one of them actually works but of course that's going to take a horrendous amount of time is there some way to find that proof more directly no one knows what seemed incredible if there was but we don't know we don't have a proof that you can and there goes on and on there are many other problems of this kind we're searching seems to be necessary but we don't have a proof that it really is so that's the P versus NP question sort of informally speaking can we solve searching problems without searching okay I'll say more about that in a second but let me first help you to see or explain where the terminology P versus NP comes from comes from these two classes of problems called P and NP P stands for the problems that you can solve quickly the so-called polynomial time problems and I don't want to get too technical about it but for our point of view polynomial time where you know you're considering how long the procedure is going to run in terms of the length of the input to the procedure and it only grows by a polynomial number of steps compared with an exponential number of steps which is what you would need if you had a searching problem polynomial time is considered fast so the P problems are the ones we consider to be quickly solvable those are the ones that don't need searching in contrast with the NP problems those are the problems which in addition to that our problem might involve searching ok so the P problems are the problems that you can solve quickly the NP problems are the problems that might involves King as well and but it's searching of a particular kind this is a little bit of a tricky point that these are problems where you can solve them by searching but once you've found the answer you can check that it's right quickly so finding it might be hard but checking it is easy so what I mean by that is think of the examples of factoring and click those are both NP problems so in the case of factoring it might be hard to find the factors but once I found them I can check that they work just by multiplying them together and seeing if I get the right result so checking is easy that's the essence of NP same with clique if I'm trying to determine does my net you know is there a net in with my network are there 100 nodes that form a clique that are all connected to one another it might take me a long time to find it but once I have found it I can check that it works that it's really a hundred nodes that they really are connected with one another and so on that check I can do easily that's the essence of NP which stands for non-deterministic polynomial time that you can you may not be able to find the answer but you can check it quickly so in terms of visually speaking both of these classes are classes of computational problems the NP problems are the ones that where you can check them easily the P problems are the ones where you can solve easily and the mathematical question is are those two classes the same is checking easily checkable problems the same thing as easily solvable problems because the easily easily checkable problems are the ones that you can solve with searching so if the two class is P and NP are the same that says that any problem that you can solve with searching you can also solve without searching so searching is always can always be eliminated if P equals NP however if we show that P is different from NP then we know that there are certain checkable problems which are not certain easily checkable problems which are not easily solvable and so that tells us that there are certain problems that really require searching can't be eliminated so you didn't follow that exactly all thing to remember is that either P equals NP which means you can always eliminate searching where P is different from NP which tells you that sometimes searching is necessary and can't be eliminated okay which is the latter is what we expect to be true but we don't know how to show it okay so this either-or situation is unresolved at this time okay let me tell you a little bit about the history of the problem in the literature anyway the you know the the subject goes back to the mid 1960s when various mostly mathematicians started looking at you know the compute the emerging computer technology and started building a mathematical theory around it and they did things like defining what it means for various in coming up with formal models of computers and measuring the amount of time that those models of computers need to solve various kinds of problems so they basically set up the mathematical framework of the theory improved a bunch of interesting theorems at the same time now some years after that in the early 1970s there were several papers by Cooke Lebanon and Karp which established the P versus NP question as an important one and the sort of this Campania notion of NP completeness which I'll talk about in a bit so it really in the literature the P versus NP question traces its roots back to the early 1970s okay but about 15 years ago an amazing discovery was made turns out that in the correspondence between two mathematicians the whole idea of P versus NP had been explored back in 1956 and that was this letter that girdle wrote Tom von Neumann which was discovered in von neumann's archives so here is a copy of the letter I'll actually explore some details of the letter in a minute one thing it's in German so that's a little bit of a disadvantage and it's also a little hard to read from back there but we'll look at it a bit more detail but just you know in case you don't know who girdle and von Neumann were girdle was is considered to be the greatest logician of the 20th century in the 1930s he had a whole series of absolutely remarkable mathematical breakthroughs one of them one of which is the incompleteness theorem which tells you that in any reasonable mathematical system there are certain true statements which cannot be proven to be true within the system and that sort of devastated certain mathematicians of that day because they had believed that anything any mathematical question would ultimately be resolved if he just worked hard enough girls showed that that wasn't true there are some things that as some in some sense can might never be known this happens to be the hundredth anniversary of you an averse three of his birth at the same time as being the 50th anniversary of that letter so it's nice time to talk about it John von Neumann was a great tremendously versatile mathematician who worked in a whole bunch of different fields in pure and applied mathematics and as well as in physics and in other fields he he was at the Manhattan Project and he was also at one of a very early computer scientist and is known for example for this von Neumann architecture that's you know sort of the way pretty much all computers are set up today is the idea of a stored-program computer so let's look back again at his letter and I hope this comes through we'll see I want I sort of focus in on a few sort of key pieces of the letter translated for your benefit and mine so it starts off Lieber Herr von Neumann this is the salutation dear mr. von Neumann and here's the date March 20th 1956 and Princeton now and one thing that sort of curious is both girdle and Vannoy men were at the Institute for Advanced Study at Princeton presumably with offices down the hall from one another so it's sort of strange that girls writing by now I mean a letter like this however you know one does have to point out that von Neumann was very sick at the time in fact was dying and died within a year so perhaps he wasn't you know around maybe he was at home and maybe in the hospital I don't know so that may have been why he wrote wrote him a letter in fact the beginning part of the letter the first page of the letter refers to von neumann's illness and girdles hopes that he recovers and so on but then he turns to a mathematical question and this is the mathematical question he talks about the von neumann he says suppose you know we have a machine it doesn't use the word computer is just a machine machine can actually use this word it's amazingly modern language in this whole letter you have to read the whole thing to appreciate it but it's it's very phrase in a very modern terminology which didn't exist back then I mean he was just make it this all up for the first time really but he says suppose we have a machine which can tell whether a mathematical statement has a proof of length n for some specified n how much time does that machine need and remember that's the question we talked about just a few slides back this is a classic searching type problem the machine can certainly get the answer but would have to search through all possible proofs of length N and that would take a long time so here is what girdle says you know D Fraga East blah blah blah the question is translated how fast does fee of n grow for an optimal machine you can sort of see it and think if you can read the handwriting there fee of n is the amount of time the machine know needs to make this test of whether the math math mathematical statement has a proof of length n so in other words if T of n is polynomial then this problem is becomes in P if V of n is more than polynomial then it's not in P so in fact really what this thing is saying this this this little section here is the P versus NP question right there kind of amazing that in a very real sense the P versus NP question has been explicitly stated in this letter then he goes on to talk about that this would be very important to resolve this question it's a very significant one way of the other and over here oops he refers to Lawson Probie Aaron which I think loosely translates to brute force or exhaustive search I think it literally means something like blind or bear trying but you know it's he's aware of this issue of exhaustive search as you know the what would if you quit anything to test if this the this proof of lengthen existed and then he goes on to mention the problem of testing formality and in fact how many steps you need to solve in general finite combinatorial problems such as like you know he doesn't say this but you find a common territorial finite combinatorial problems would be like the klique problem or scheduling problem was stuff like that so he really has a vision of what's important about this question and and really kind of predicted where the field is gone will fit with the field went over the next you know 15 20 years it's it just I think an amazing document in the history of science that this way that this thing was discovered anyway so in the 50 years since girdles letter P versus NP question has kind of attained a certain almost mythic status within computer science field within theoretical computer science it's kind of not as thought of as the holy grail problem of theoretical computer science and also within the mathematical community it's considered to be one of the great problems in contemporary mathematics you know the Clay Institute has been responsible for this list of kind of great math problems the this I guess they organized the committee of folks and I'm not sure I know the whole full background but they there was a group of mathematicians who put this list together in the year 2000 sort of patterned after the list that Hilbert put together a century before these are eight unsolved problems of mathematics today which kind of our challenge problems for mathematicians for the coming century and as you can see P versus NP problem P problems one of the problems on this list I was happy to see that and one thing that's different between the clay list and the Hilbert list is that the clay Institute is also offering a million dollars for the solution to any one of these problems so that's a pretty nice thing and you might notice that the top problem on the list has a little check mark there it doesn't have a bullet anymore because that problem has actually been solved you probably know the story of Perlman I'm not going to get into that whole complicated mess but he didn't accept the Fields Medal a few month ago or so and even though he's the one who solved this problem and it's not known yet whether he's going to accept a million dollars that has not been it is a sort of a two-year delay before they before they give the million dollars out I guess it's a little bit more than just you know gotta be careful with those million bucks uh so so anyway so that's you know after I had to guess I bet he'll he'll accept this one that it but I actually I really maybe not who's to say so yeah oh yeah so before I get to that I want to say one thing about P versus NP getting back to that question some sense the P versus NP questions that do you really need to search when you have a searching problem and you know in some sense you know if you're you might think that's kind of obvious obviously you need to search if you have a searching problem and you know believe it or not I get a couple of times a year I get a manuscript if someone purporting to solve the P versus NP question some reason I'm a and I get sent these things why and they are invariably even though they like 40 pages long all they the the the the essence of it is the problem is obviously true that's the content pretty much always in these papers and you know there's a lot of complicated calculation but they basically all say well you have to solve these problems by searching and searching takes a long time calculate calculate calculate so what I want to show you is that sometimes you can avoid searching where you I think you would otherwise need it and I'm not going to be able do that in detail because it would get too technical but I'm going to give you a little bit of a flavor why they have how that might happen and that's the case of testing whether a number is prime okay so this is actually the one of the problems that you know the problem that girdle mentioned in his letter as one that might seem to require searching and it's superficially the only way the way you would test if a number is prime is the same way you would factor a number you would do trial division of lots of possibilities and if you if you fail to find a factor then you know the numbers prime if you find a factor you know it's not prime but there that's very slow as I pointed out that searching type method but this is where we now know that there are dramatically faster ways of testing if a number's Prime and I'll give you a little flavor of how that goes and these also to rest on a centuries-old theorem due to form ah in number theory and you know this is as technical as the talk is going to get so I would say this is a technical I keep on pointing at my my laptop they which I know you can't see this is a ah okay let's just let me walk you through this I mean it it's worth trying to figure to understand in this because it's very nice so try to bear with me what this theorem says that if you have a prime number P like take seven for example and you have a natural number a lectin P like take two for example so P equal to seven equal to two then if you raise a to the P minus one power you always get one modulo P and saying that in English it says that if you take the number a which is two in our example you raise it to the P minus one power then you divide by P and take the remainder so throw away the quotient but only look at the remainder after you do the division you always get one for the remainder so let's actually work ourselves through an example so if P is seven and eight 2 as I mentioned you raise two which is a to the seven minus one or six power which is 64 now you divide by seven and take the remainder now 63 is the multiple of seven so 64 has remainder one when you divide by seven whoops okay and it works whenever you meet the conditions of the theme for any prime in any a it and and any such a you always want to get one which is actually kind of you know so you might think big deal but it's kind of amazing that this works if you actually try it out on a bunch of examples and just in contrast if you try an example where the where P is not prime you'll see it fails to work so if you take P equal to 15 and able to two then you raise two to the 14th power you get 16 384 and you divide by 15 and take the remainder you get four which is not one so you see that equation fails in the case where it can fail anyway when the indicates where P is not crime and what's amazing about this is that that calculation that I just did proves to you that 15 is in prime not because we knew that already but this proves it to you in a different way it doesn't prove it to you by exhibiting the factors 3 times 5 of P it proves it to you by saying well P fails to have a property that we know prime numbers have and therefore it can't be prime and the thing is is that you can use this as a basis of a test basis of an algorithm which can test prime ality without going through the factorization process and in fact you know initially it was a randomized algorithm and since you know it's been since sort of you know with lots of additional ideas that made into a deterministic algorithm and now we know that the problem of testing of a numbers prime can be solved quickly in polynomial time ok so searching can be eliminated ok now let me tell you a little bit about this notion of NP completeness alright I would say NP completeness was was perhaps the first and maybe the only important step that's been made towards solving the pn NP question and this is not it's a nice kind of explainable idea it's kind of amazing in its own right when NP completeness is this it tells you that the the that the problems in NP the searching problems are in many cases linked to one another and what I mean by that is if you find a way of solving the clique problem remember this you know this problem with the network of nodes if you can find a way of solving that problem without searching you immediately get a way of solving the factoring problem without searching even though those two problems don't look anything like one another whatsoever a fast way of solving clique will immediately translate into a fast way of solving factoring why would that be true well the reason for that is that there are these transformers that can convert factoring problems into clique problems so if you have a fast way of solving the clique problem and you want to solve your factoring problem you just push it through the transformer transformer things around thanks for a while and spits out a clique problem I can do that again if you want and the nice thing about the clique problem that gets spit out is that if you find a large clique in that network that gets produced it immediately translates into the factors of the original factoring problem so you get the idea that's why these the clique problem is related to the factoring problem this way and incidentally the reverse transformation is not known to be true so we don't know how to convert clique problems into factoring problems only only this way however clique is still this this phenomenon is not unique to factoring in that you can convert any NP problem to a clique problem so what that tells you is that clear the clique problem is in some sense the granddaddy of all problems in NP because you can convert any NP problem into a clique problem and therefore if you can solve the clique problem quickly you can solve any NP problem quickly and then P equals NP that's what it means for clique to be in it's not the only one there are many other problems which are np-complete but clique is a you know one of the problem we were looking at okay oh yeah so let me also mention a little bit more about NP just to sort of clarify what's going on with NP a bit you know I said that NP are the problems that where you can solve by searching but where you can also check the answer quickly so just to contrast that there are certain problems that you can solve by being able to check the answer quickly it's not a given that just because you can solve it by searching that you can always check the answer quickly so take the case of chess and you want to know which side would win under optimal play if both sides played perfectly would white win with black win or would it be a draw nobody knows the answer to that problem in principle you could figure it out by going through the entire game tree of all the possible games that you can have in chess but that's an astronomically big number you know and we take horrendous amount of time longer than the lifetime of the universe and so it's not practical to do that but moreover suppose you did it and you determined White has a forced win if the both sides play optimally now you want to convince me of that now you want to check that that's the right answer there's no simple way to check it the only way to check it is to essentially walk the world the whole thing do the whole thing over again okay so that's in contrast if I'm trying to get the sense that this is a search of the seeing which side has the win under optimal play is a searching problem but it's not an NP type searching problem it's kind of in worse than NP because you don't even have this feature that you can check the answer quickly okay so just sort of summarizing some of the information that we've been discussing recently we have the classes P and NP and the four problems that we've discussed multiplication factoring clique and optimal game strategies are kind of appropriately placed the games is outside of NP clique and factoring are in NP but not known to be in P and actually in all of these cases this is just conjectured the conjectured picture things may collapse down and multiplication is known to be in P now complexity theorists have been working on the P versus NP question you know for 30 years or so but they've been doing lots of other stuff too not just beating our heads against the wall on just that one problem the whole time and one of the things that was done is to devise even more complexity classes and in fact a rich system of classes that capture all sorts of features of complexity of different problems so there's actually a rather rich kind of I don't know what to call it a classification system for computational problems according to all sorts of different parameters the amount of time you need the amount of space you need whether you can solve it more quickly with parallelism or randomness and so on and it's been populated by different problems that we you know these are real problems that people are interested in solving that occur as far as we know it is within this hierarchy now and I also want to mention that this hierarchy is by no means a static object the things are changing certainly if P was proved if equal to NP that would affect the Sadd achill II but there are changes that are occurring every few years as new discoveries are being made so for example if you if we focus our attention on the prime ality problem you know as I just mentioned it's now known to be in P but if we just turn black back the clock a few years we would only know that primary would be solvable in what's called randomized polynomial time and it was this result that came out in 2002 that moved prime ality down one step lower in the hierarchy okay so got this P versus NP problem what can we do about it you know for one thing you know I write on the side how do we prove P different from NP that partly reflects my bias I don't believe P equals NP I don't believe that we can solve search problems without searching I believe that as most you know I'm not unique most of the other people in the field feel the same way that some of these many of these problems really do require searching we just don't know how to prove that and then why why why is it so hard to prove well the reason is that computers or computer algorithms can operate in very clever unforeseen ways just like in the case for primality testing there's all sorts of devilish fiendish bizarre ways of solving problems that we may not have thought of and it's very difficult to prove that none of those can possibly work in a sense by proving that none of those can work the computer kind of becomes your adversary you want to show that this potentially fiendishly clever machine no matter what complicated thing gets programmed to do it's not going to be able to successfully solve one of these searching problems it's such a rich class of possibilities very hard to get your hands on that and show that none of those can work so what do we do so here's a strategy that myself and some other people have taken on over the years is try to limit the power of the machine like kind of handicapping it in some way okay and then for this handicap machine it can't run anymore totally limp and when you have a machine that can only limp maybe you have an advantage in being able to prove it's going to have you know you're limiting the kinds of operations that can do you're limiting its behavior in a certain way and maybe for these limited machines you have a better chance of proving that they really do need to search there are fewer clever things they can do if you are unsuccessful limited even further until you've got the things so limited that you can finally say something and hopefully you get some insight by doing that and then maybe you can start eliminating these limitations and you work your way up because it's hard to tackle a very hard problem from nothing you would like to break it down into a series of steps if you can and you kind of eliminate these handicaps one by one and hopefully you can build back up to being getting an idea of how to tackle a general machine which is unlimited that's the hope anyway okay here's another approach well you know here's a in combination with that here's an approach that people take is they're trying to figure out a way of finding an input to the machine on which the machine would fail so here's you know a machine that operates quickly it doesn't search so presumably this machine is not able to solve say the clique problem but how do you prove that it doesn't saw it can solve the clique problem you know if it's not able to search well you want to find some kind of an input an example of a clique problem which particularly difficult and you know you're more likely to find difficult problems among large problems it's only saying it's somewhat mathematically if you're trying to exhibit the difference between polynomial time and exponential time behavior you better looking at large n because then the difference becomes even more clear and kind of carrying that to the extreme it might make mathematical sense to try to run the computer on infinite inputs if you could make sense of that and I think in some ways you can and maybe by running the thing on input infinite inputs you can get some insight into what makes the problems hard and learn something back about the finite case you know again none of these things have paid off otherwise that would be giving is a different talk today but those are ideas that people have tried ok so drawing to the end of my talk will the P versus NP question ever be solved but it seems clear that the collection of techniques that we have at present is Natick is inadequate we're gonna have to develop new methods in order to be able to to tackle the P versus NP question let me just tell you I mean I'm personally an optimist that it will be solved one day let me tell you a little story about that when I was a graduate student back in the mid 70s I made a bet with one of my fellow graduate students happens to be Len Adleman who was the a from the RSA code this is before RSA Koch was developed it's which stands for Rivest Shamir and Adleman to give everybody credit by the way if they're here so so Len I made a bet with Len Adleman we were both thinking about the P versus NP questions is you know 30 years ago and I made the bold claim that the P versus NP question would be solved by the year 2000 and I bet Len an ounce of gold which was a lot of money for a graduate student well I paid off luckily the price of gold when I was a graduate student was around seven hundred dollars an ounce now it's around $600 an ounce when I paid off it was around two hundred and fifty dollars an ounce so I got lucky there but but you know that's anyway that's that's my story um and I don't know I think you know I'm still hopeful that you know we'll see the solution I it's a great problem and and I'm looking forward to to seeing what happens with it so that's the end of my talk thank you thank Michael for a really fine talk and I think we can take a few questions yep yes sure meaning it is you know if you're willing to settle for less than the best in many different senses then you can solve these problems in some cases quickly so if you're willing to settle for an approximate solution instead of finding the biggest clique well clique is probably not the best example but I mean there are other because in the case in some cases it's known that even getting an approximate answer is as hard as getting the best answer but as scheduling might be a better example I'm not an expert approximation algorithms but there are cases where if you're willing to settle for an approximation to the best solution then you can do it quickly but yep maybe I should just leave it at that is that good enough for you yeah yes ah this is Sudoku Sudokus whatever it's called yes I said np-complete ie yes yes hahahaha thank you actually I don't know but it claimed that the answer is yet yes in the back there don't you well if is there a distributed computer that can solve it well me if there is a distributed computer with a moderate amount of processors you can simulate that with a ordinary sequential you know single processor computer just by you know that one one machine just taking or pretending to be each one of those distributed machines one at a time so it's not going to change things tremendously unless you have an enormous number of distributed machines available to you like an exponential number of distributed machines so yeah then that case the problem would be simplified but it you know in a sense that is an impractical number of machines to throw at the problem you know you're talking about you know instead of working for 20 computer years of effort you might have to have you know quadrillions of computers or more than that you know working time working in parallel so it's you know it's it doesn't really buy you anything that's going to change the picture dramatically yes yes right right yeah I was trying to be careful when I made my actual statements to about NP so the question is there were two slightly variations of one another in terms of the Khaliq problem am I just looking for the largest possible clique in the network or am I looking for a clique of a certain specified target size the the latter is the one that's in NP the other one is not an NP problem because you can't check that you have AK you can check that you actually found the biggest one that's not an NP type check to make but if you can solve one of them without searching you can solve the other one without searching they're both very closely related computational problems and that was sort of using them interchangeably depending upon you know what sort of work best in the sentence one last one last question yes yep that's a great question I like that what makes me think you know does girdle had mentioned that there are certain questions which are you know perhaps unsolvable in in mathematical systems maybe P versus NP is one of them and certainly there are people in the community who subscribe to that possibility who think in fact P versus NP may be just one of those questions that can't be resolved there's no at least in terms of proving it one way or the other and you know I can argue that both ways my personal view is that you know it's a very concrete down-to-earth kind of a question it's not the type of question that you would normally think of as being one which is independent of axioms like the axiom of choice or you know the continuum hypothesis which concerns infinities and things that are very far away from ordinary intuition it's a very kind of concrete question P versus NP and for that reason I think you know that IIIi don't know there's anything to back this up but I think that kind of question is more likely to be one that's going to get resolvable within our axiomatic system on the other hand there is something kind of somewhat close to the foundations of mathematics in the P versus NP question you know just by virtue of if you think of that girdle himself was a logician was thinking about it when you're thinking about algorithms it's close closely related to the notion of proof and then you're talking about logic and it is true that questions in logic are more likely to run into this danger of unprovable ax t and so that gives a little bit of credence to that possibility but my personal view and it's just an opinion because nobody knows that that it is solvable and there will be solved someday though I'm not taking any more bets well thank you thank you very much for coming you you

Channel: PoincareDuality

Views: 149,127

Rating: 4.9196324 out of 5

Keywords: harvard, math, Harvard University, mathematics, clay, institute, public, lecture, MIT, P=NP, Problem, Computer, Millennium, Prize, Problems

Id: msp2y_Y5MLE

Length: 61min 38sec (3698 seconds)

Published: Wed Nov 23 2011

Reddit Comments

[u/MKLOL]

What I realized while watching this video.

[meta]The professor is like a solution checker (he can check if a NP vs P problem is correct in a couple of days) but cannot give a proof in acceptable time[/meta]

[u/TimmT]

The topic is an important one of course, but personally I find it hard to get excited about things that are unlikely to be solved during my lifetime :\

Side note: the part he had trouble translating ("bloßes probieren") would translate word-for-word to "mere trying" (i.e. merely trying all possible combinations). I'm a bit surprised that there is no official translation for something as important as this.

[u/tripstuff]

This guy actually wrote the textbook that I'm going to be tested on at 8:00am tomorrow. Cool.

[u/theTechHippie]

Sipser wrote my theory text book, too.

[u/[deleted]]

comment

[u/umlal]

I was playing chess while watching the lecture, and even before he mentioned the game strategy, I figured there must be "some best way" of advancing towards a solution. I was thinking strategy, I was thinking instead of searching each solution, minimizing the act of brute force might do the short-term trick, I'm not saying its a solution but rather our-time-fix, I mean if you take for example O(nⁿ⁾ but only when n is a prime number you might reduce the options significantly, or use other multiplication rules to eliminate some options.