The History and Status of the P versus NP Question

all right welcome everybody once more month a new colloquium I'm very very pleased to have with us professor Mike SIPP sir from MIT you're the the head of the theory group in the applied math department of computer science department a pi PI math department but head of the theory of computer science group there and today he is going to fill us in with some of the details in the history about the P versus NP question maybe the most well-known question in computer science theory I'm going to pass this to you I just you kind of clip in your pocket thanks sorry so this is a cool place and I mean you guys are studying theory this month all right how's it going good it was there another and was there another prerequisite course to this is there in like a discrete mayor for people coming in basically this is the okay okay I need some of this stuff for an album tour we're in the we're in the course is the theory is this at just at the beginning of the course now we're doing finite automata and that kind of stuff okay chapter what Chapter 1 okay alright well this is a little bit of looking ahead ok so I'm going to talk to you today about this thing called the P versus NP question as I mentioned this is a pretty famous problem that came out of theoretical computer science and has you know percolated its way over into the mathematical community to know many of you know about a year ago there was a place called the clay Institute who was set up to fund various projects in mathematics and they announced a prize of a million bucks for the person who solves the P versus NP problem or any of six other mathematical problems like the Riemann hypothesis for the Poincare a conjecture would whatever those are I'm not going to talk about those today but anyway this is you know it's a nice problem it's maybe the youngest of all of those problems and I'm going to just tell you a little bit about where the problem came from a bit about the significance and kinds of things that people have done to try to solve it a bunch of related matters to sort of spreading out touching on other topics in complexity theory which is the area connected to this problem okay the first of all what the world is the P versus NP problem I guess you've bumped into it in an algorithms course you haven't seen it in the theory class yet in a nutshell the P versus NP question asks its concerns problems you want to solve on a computer certain kinds of problems you can solve really quickly other problems even on a very fast computer seem to take an incredibly long time how come well certain kinds of problems that seem to take a long time involve searching for the answer over a large number of possibilities let me give you an example suppose I take two big numbers and I mean huge numbers each of which has say 500 digits so I'm not talking about a number which is like 500 I'm talking about a number which is 10 to the 500 some astronomically big number more than the number of particles in the universe by a long shot and you take those two big numbers and you multiply them together to get any an even bigger number but now with a thousand digits now even though those numbers are pretty big the multiplication process is something that you can do pretty easily at least with a personal computer you could there's a simple algorithm for multiplying the two numbers using just the same method that you learned in grade school and that would give you the result in less than a second but suppose you wanted to do the reverse process namely start out with a thousand digit number and recover the two 500 digit numbers that were multiplied together to give that thousand digit number so I'm gonna give you the answer and I want to know what was the problem in a sense that's the so called factoring problem so the reverse of multiplication and that factoring problem is incidentally important for various cryptographic schemes RSA I don't know if you know anything about you know run into some of that stuff but this is an important problem both from a theoretical point of view and also for certain very practical reasons this factoring problem the question is you want to carry out you want to implement the factoring problem on a computer so that the computer will actually do that factoring for you the bad news is that the only way essentially that people know how to factor numbers is to use trial division try dividing by two by three by five at least you can confine yourself to the prime numbers so that'll save you a little bit but it's not going to save you enough to allow you to just to go through all the possibilities up through numbers with 500 digits at least it's not going to save you enough to be able to do that within your lifetime or the lifetime of the universe because that's a huge number of possibilities that you would have to try in order to do this solve that problem using roots the brute force approach now maybe it's possible to factor numbers without resorting to that simple-minded brute-force approach maybe you could just home in on the answer through some magical formula where you put in the thousand digit number turn a little crank do a little calculation outcomes the 500 - to 500 digit numbers conceivably that could happen and then you'd be able to factor numbers much more quickly without searching nobody knows whether you can do that or not that's a very famous and very important unsolved mathematical problem which is closely related to the P versus NP question because what the P versus NP question really essentially asks is whether for any problem which can be solved by searching is the brute force approach really necessary or can you always somehow avoid it there are certain kinds of problems for which you can solve them with brute force but you're going to also find the salom through a more direct way much more quickly but what P versus empty ask is whether you can always do that well you can always shortcut your way through the brute-force approach and find a solution which gives you find an algorithm which gives you the solution more quickly and is that this comes up in all sorts of different places for example you know if you want to if you say a university not a big university not this one and you have lots of different classes and people taking final exams or whatever at different times and you want to arrange a schedule where you're going to minimize the number of conflicts that the students are going to have that's a very reasonable practical problem that people are faced with and have to solve sounds like the perfect one for the computer you just feed in all the constraints let the computer turn its crank somehow and spit out the optimal schedule bad news the only way that people know how to solve that problem is to brute force search your way through all possible schedules if you really want to find the best answer you're going to be satisfied with something which is close the best maybe you can do better but if you want the best answer no one knows how to do that within a reasonable amount of time nor does anybody know of a way to do that to prove that you can't do better so that's the question can you always be grouped for search or is it sometimes really necessary that's P versus NP and it's related to problems in mathematics problems in you know optimization as the scheduling problem is problems in computational biology you want to find different ways that proteins fold up and you want your you know amino acid sequences fold up and you want to find the one that has the minimum energy because that's presumably going to be the configuration that ends up occurring you know inside the organism as it stands right now people don't have very good methods for doing that and one approaches the brute force approach but there are so many different configurations to search through that's still not very practical and there's many many in physics as chemistry there's many different areas in science and engineering and more broadly where the question of brute force search hoot for search is a problem and you'd love to be able to get rid of it but no one knows whether you can in general so mm-hmm what I'd like to do is okay first let me tell you a little bit why we use this funny terminology P versus NP to refer to this question about brute force search so P stands for polynomial time and really what it means is the class of problems that you can solve quickly without searching because searching is going to involve an exponential number of possibilities that's I mean the that's in the cases of interest anyway that's an exponential first is a long time so polynomial is something that's a modest amount of time and P the P class is the class of problems that you can solve quickly in contrast with the NP class those are the problems that can be solved using searching so you want to know is the product class of problems that can be solved using searching the same as the problems that can be solved quickly so therefore you would be able to always eliminate the searching by moving it by through P being equal to NP or perhaps P is different from NP and there really are problems where the searching cannot be eliminated so that's really the basic question of P versus NP is P equal to NP namely you can always eliminate searching or is P different from n P some problems really need certain need to be searched through by Murphy's Law P is probably not equal to NP because you know it would just be too good to be true that you could always solve all of these problems quickly probably some of them need to be searched but no one knows how to prove that and that's really what it comes down to is trying to find a way to prove that is no clever way of solving certain problems you need to search okay or maybe they're equal so what I'd like to do in it next is talk a little bit about the history of this problem because up until about 10 years ago people generally trace the roots of this area to the 1960s both in the West and then also in the Soviet Union there were kind of two parallel developments where people were starting to look at the number of steps you need to solve various problems computationally and the issue of brute force search sort of a row as an early consideration but remarkably about ten years ago there was a letter discovered from the from the 1950s from 1956 to be exact where this exact question was raised and the letter itself is a kind of remarkable letter it's a letter from girdle Kirk girdle who was a famous mathematical logician to John von Neumann who was you know one of the you know also mathematician in play dick played a key role in early computers and so a girl wrote this letter to of anointment essentially and among other things talking about this P we didn't call P versus NP he talked about the question of being able to eliminate brute-force search I have that letter here it's going to be let's take a look at it because I think it's so cool bad news letters in German but I'll translate something see if you can focus a little bit I don't think that's terribly interesting somebody was searching through von neumann's archives which were in the Library of Congress and said well this is interesting and they said it went through a chain of people to yours heart Manas who was was one of my teachers actually Cornell when I was an undergraduate and he published a very short note saying this letter been found I thought wow that's really amazing and so I asked them for copy that that's at least what I know about the discovery of it so this letter starts out Lea bear hair of anointment it's very formal may that's why every all German letters are started I don't know but and he starts out and then you know a hub of MIT and my German is almost non-existent hug me gross and Duncanson air crackling get hurt which is he talking about von neumann's illness in fact if I no one was dying at that time he died not that long after receiving this letter I think my nothung same connection but and so he talks a little bit about the he's you know hoping that these various treatments are going to help von Neumann and then he says well whatever you know let's turn to some mathematical questions and right and so then he raises he raises goes Lawrence's right into this question about brute force search and what so I think you know maybe you haven't come far enough in the course to appreciate this but I think partly partly also what's so amazing about this letter it's just the terminology that he's using which is very modern in terms of measuring the number of steps you need that an algorithm needs in terms of a Turing machine for example that was something that was only done in the Linton in the literature ten years later but okay so he concerns that he's considered the following problem it's a mathematical question he says suppose you have a formal mathematical system let's not I'm going to get into too many details about logic here but you want to know if you have a mathematical statement one of the one of the great accomplishments of mathematical logic was in formalizing what it means for a mathematical theorem to have a proof okay you know proof is what mathematics is all about you know at least two mathematicians for the most part I guess you want to know you know that that's the way you determine truth or falsity we don't do experiment so much you prove things and that's proof is you know sequence of logical arguments which can convince which makes a convincing case committing arguments that a certain statement is true or false okay so one of girdles great achievements was to show that there are certain mathematical statements which are true but don't have a proof which went and was totally shocked the mathematical community of did his day which is the 1930s at the time because you know great mathematicians like Hilbert believed that nothing would remain unknown in mathematics anything true had a proof and would all you could all if you just look hard enough you'd find it so girls show that there are some things that are true but can't be proved and I can say more about that later if you're interested because that in itself is a remarkable thing but anyway if you restrict your attention okay so another problem you haven't covered undecidability yet but if you want to know for a given systematical statement does it or does it not have a proof you might imagine trying to answer that with a computer but that's something that's beyond the power of computers to decide that's an undecidable unsolvable problem so that's not you know just doesn't does a statement have a proof or not that's another one of these undecidable problems however if you want if you restrict your attention to say does a statement to have a proof up to lengths of thousand then it certainly decidable because all you have to do is try all possible proofs and you can check whether you know check whether a string constitutes a legal proof or not that's part of what we mean by proof you can always check to see whether it's a proof so you can just try all possible strings one after another and see if any one of them is a proof of the state of the statement and since you only have to go up the length of thousand you can certainly do it in finite time however that as you can see is one of these brute-force type approaches and what girdle was asking Vannoy minh is whether you can solve the problem of testing whether a statement has a proof upto length n more quickly than searching through all the possible all the possible possibilities up to length n I'm not maybe I even gonna skip the technical way he puts it but he really he asks whether it can be perhaps ed conceivably you can even you know fear of n is that is the time involved for the fastest machine to determine is there proof of length n in general he says maybe you can do that in time K times n for some K which we would call linear time or maybe you could do it for a KN squared sort of almost getting at the idea of looking at different polynomials so he says it's conceivable he and he it would have tremendous implications for mathematics remember where he says that maybe it's down here it said it would be very important for mathematics to decide what to decide whether or not you can solve this problem without using brute force search how does he call boot for a search he calls it the embossing Probie errand blind the probing this was his term for brute-force search and he goes on to talk about other problems besides testing if something has a proof he talks about for example testing of prime if something has a prime number or in general for finite combinatorial problems whether or not you can eliminate blouson probiem okay there right down here whether in algemene that's in general whether you blossom Probie aaron can be eliminated and then he goes on to talk about some other stuff which is not that relevant to us he mentions this post's problem which is kind of a cool thing too if you get further on in the subject you know you know there's problems which are decidable and there's problem which are undecidable and supposed problem there's a certain sense which you can ask is this something which can be kind of in between and that was an unsolved problem back in those days in the 50s and an 18 year old named Richard Friedberg got the answer to the problem and so he's writing asking did you hear about Richard Freiberg solution to this post's problem it's the same post that you know that's in the post correspondence problem which I mentioned in the book by the way and and then he said unfortunately Friedberg father insists that he become a doctor he's not going to go into mathematics what happened and then he signs it you know Crick girdle yeah I know III think this letter is really just an amazing discovery in history of science about you know thinking about that time among two great guys at least you know it was girdle about this very fundamental problem and subsequently this was you know in recent years there's a prize in theoretical computer science called the girdle prize and the reason for naming it after girdle was because of this letter no-no-no regno unknown whether he thought about it or answered it or anything well von Neumann was a smart guy but you know I have to say this has been other smart people since then and we well we'll see let's see where does let's take us a little further into the present so this is a brief history of P and NP and in general sort of the complexity theory area so 1950s is girdle's letter and the 60s was really the birth of complexity theory through people you know Michael Rabin who's at Harvard Manuel bluml with my adviser Hardman as I mentioned various people were set up the whole I the field of measuring the number of steps that you need to solve a problem how do you classify problems just turning that into a mathematical discipline and there's this notion of NP completeness enough the slides a little bit small and the P versus NP question was basically in the early 70s by cook and Levin and Karp 11 was in the Soviet Union and cook and Carper here in the US actually cook woods maybe in Canada at that time yeah in the American in the West in the West yeah loving his be enough that's right so they basically formulated the P versus NP question as a mathematical question and there was various attacks that were basically didn't go anywhere in the early 70s and a you know and up through the beginning of the 80s on P versus NP but what was there was not really much progress made on that problem seinem cliffs been much progress made on the problem at all since it was proposed but one area where there has been a lot of progress is in terms of setting up a classification system in complexity theory for various computational problems and just to give you some sense about what that looks like you know as I mentioned there are these two classes P and NP well there are many other classes that have been investigated and proposed so P and NP might slide there red but if somebody's making my black here this P and NP here are the two classes I mentioned these are the P is again the class of problem that you can solve quickly and P of the problems which might involve searching and there's a whole bunch of other classes that have been investigated both inside P and beyond NP and there's there are many interesting questions that are not solved in some cases about the relationships among these classes but what isn't very nice is that lots of math lots of problems computational problems that people had been investigating turned out to fit very nicely within this classification system I'm so like multiplication and addition testing if there's a path for one point to another in a graph computing the determinant linear programming you probably saw that in algorithms course those are all problems that can be solved but within different levels of the complexity hierarchy inside Paul you know quickly inside P and then there are other problems which seem to go further out in difficulty what I'd like to do I hope it's not too ambitious is to try to give you a little sense now of the kinds of things that people have tried to do to South PN NP and you know by the way you've been a very quiet despite what I was promised audience so here is where it may get a little bit more technical and don't let me lose you because I'm not I'm gonna try not to say anything that can't be explained in a few words okay so didn't get it through it's my fault feel free to jump in okay so when investigating problems like P and NP and trying to determine how much computation you need to solve a problem one of the things that's nice to do is to work with the simplest computational model that you can come up with because you know you could try to develop your mathematical theory about you know your Sun SPARC station or whatever the current thing is your Linux box or you could try to work with something simpler like a Turing machine because it's advantageous to try to set up things you know your your basic underlying formalism its crisply and as simply as possible and not to be a I'll prove something about it so here that I'm gonna propose to you the the model of computation that people in my area generally think about and that's called the boolean circuit if you ever run done any hardware design you've seen these things already because all that I have in mind here in red are variables which can take on the values 0 and 1 or true and false if you want wires here that can carry the truth-value you know the the assignment to the variable up to one of these blue blue objects and those are like mini all those are called gates though those computes very simple things so maybe this is all stuff that you've seen already so this is a and gate that computes the end of the things coming in and spits out that value and this is an or gate that computes the or of things coming and spits out that value and so and here's the negation and so what we have here is a representation for a certain computation a certain kind of a function you put in values into the variables those five variables here you you propagate up through the circuit and you get a value here up the top which is the output okay is that because I'm going to spend the next like 10 minutes talking about circuits so if you didn't buy slowly flow and where the circuit is if you didn't see it before okay so now what's going to be important to us are measuring the measuring certain parameters of the circuit for example the you know counting how many gates does a circuit have or how many how many levels does the circuit need to do a certain computation things like that that's what's going to be important when we're considering the complexity of a function so in particular what I'm going to be interested in for certain functions that I may want to compute down here how many gates do I need because it's going to turn out that the number of gates you need to compute your function is closely related it's in the amount of time you need to compute your function on a more standard model of computer computer those two things are very much tied to each other seems a little bit perhaps unintuitive that gates on the one hand should correspond to time but maybe it would help you a little bit just to realize that for the particular kind of circuits I'm considering you're not allowed to have loops so all you know information has to propagate through the circuit and so in a sense you can imagine the more gates you need so the more time for propagation you're going to need maybe you might think about is closely more closely related to the depth in a certain sense that's true but don't let's look at it with fuzzy glasses for now okay so the the size of the circuit is going to correspond roughly speaking to the amount of time it's going to be close enough for my purposes okay so let me here restate what I just said there is a close relation with time complexity for the circuit complexity namely the number of gates that you need is closely related to the amount of time you need and there's a theorem that says for any function f that's being computed you can compute it in a certain number of steps I'll say a Turing machine if you can compute it in that number of steps then it has circuits with that number of steps times a logarithmic factor gates okay so flipping that around if you want to prove that a function is not in P so that function cannot be computed with a polynomial number of steps that means that you have to show that it requires more than a polynomial number of gates okay yeah okay so maybe I'm being a little bit too short winded in my slide computable and Tien steps on a touring machine so I'm mixing two different models now I'm comparing time on a Turing machine with number of gates in a circuit so entering machine is supposed to be our proxy for like a workstation so computable and Tien steps if you want to think about it as you know on your favorite comic computer model if you can do with net number steps then you can compute in a circuit with slightly more gates than that number of steps so if got that you just have to add in this extra logarithmic factor you know for our purposes ignore that so if you can do that with some of the steps you can compute it with that number of gates roughly speaking so you can flip that around because really our whole hope in trying to solve the P and NP question at least you know 99% of researchers in the field believe P is different from NP and so whether that would amount to is taking a problem like factoring and proving that it's not solvable without good force so therefore it's not in P and that would mean that any procedure would need more than a polynomial amount of time to solve it that's what you want to do trying to show that your problem needs more than a polynomial amount of time and by virtue of this theorem it would be enough to show that it needs more than a polynomial number of gates okay I'm not losing it here because the whole direction of the field at least for the past you know 20 years has been to try to understand how to prove circuits need lots of gates just want to say a little bit about because there's you know basically it's mostly kind of kind of bad news that I have to report bad news is that we don't know how to prove circuit see lots of gays because we did we would have solved the P and NP question and in fact the state of knowledge for proving circuits need lots of gates is extremely weak we know how to prove there are functions that have n inputs in order to solve the P and NP question well either a function which have n inputs where we can prove you need like five n gates we don't even know how to prove something needs a hundred n gates but the South P and NP you'd have to prove that the circuit needs more than N squared gates or n cubed gates for any polynomial you know end to the end to the end to the million you have to prove it needs more than n to any power number of gates whereas the state-of-the-art is to prove that only needs five gate five and gates so we're way off from what we need to be able to do but what had happened oohing with all this time so what people have been doing is looking at circuits which have been restricted in certain ways it's kind of like this just you know going back to workstations as you're a computational model you want to prove your workstation needs lots of time to solve the problem don't have to do that so let's do something like pull out a bunch of the wires not enough so that it completely breaks but so this has to limp along you know doing its computing so now with this sort of wounded machine hopefully you have more techniques available to prove that needs more time it's like you tie a one hand behind its back now it has the Dino compute you know just with a limb much more limited set of capabilities and when you do that people have had more success in proving that the circuits in this case need to be large and that's the way mathematicians often work is that they can do they have very big problem that they're trying to solve they can't do it they try to look at you know some smaller cases some simpler versions of that problem where hopefully they can solve it in the simpler case and in so doing hopefully learn something which might be more useful generally okay so the two cases I alluded to here are the so called monotone circuits let me just say what those are and the bounded depth circuits so in the case of monotone circuits you you look at what that what is the power of the circuit when you eliminate negations those these circles have ands and ORS only they can still compute lots of interesting things but for such circuits it has been shown that the circuits need to be very big to solve problems that you know the the problems that we're looking at okay so the negation somehow seemed to be key exponentially large more than polynomial so that's what you need you need the you know the the goal here is to prove the circuits on n inputs have more than polynomial or hopefully even exponential in n size to solve you know these searching problems if you do that you're golden now that the whole the theorem decayed you know the good news is that we can say something here the bad news is no longer any connection with ordinary Turing machine or standard computing time so you know this is a very nice theorem and the guy who solved it got a big prize for doing it but I didn't really tell us what we want to know about bu an NP but you know maybe we learned something along the way obviously not enough but still its progress let me talk a little bit about down to depth circuits which is something actually I personally work in so these are circuits where you limit the number of levels and perhaps four circuits with a limited number of levels as a kind of a handicap a kind of you know tying this hand behind the back of the circuit you have a better chance of proving the circuit needs to be big and that was successfully carried out and in this case I can be a little bit more concrete about the theorem that we showed if you take the here tears a concrete result that we prove if we consider the function which just counts the number of ones among the input and tells you whether it's even or odd it's the so called parity function and you want to make a circuit which computes that function well if you allow yourself logarithmic depth it's not too hard to come up with a pretty small circuit in fact that's the circuit that you would probably come up with if you played around with it on your own a little bit to compute the power you would sort of make a tree of like exclusive or gates which you could then implement with ands and ORS if you wanted and they would all sort of fan together and the whole size would be linear some constant times n and the death would be logarithmic now but suppose for the reasons of trying to learn something about circuit complexity you restricted your depth say all the way all the way down to depth to so with the circuit would in that case look like just an end of ORS or variables or negated variables in that case it's easy to prove that the circuit needs to be exponentially big not going to do that right here but you can show that for depth to circuits exponential size is necessary and the question that me and a few other people looked at was what happens in an intermediate case suppose you consider depth 3 or depth 12 is it conceivable then there you could solve it with a polynomial number of gates or maybe circuit still needed to be very big and the theorem that we proved was that for any depth D the paradis circuits need more than polynomial size and there was a number of interesting ideas that came out to there and we'd probably don't really have time to talk about it here which I think possibly could say something about applications to problems like PN NP anyway this know now it's a D is constant good question D is constant in order to get this theorem now as you allow D to be growing like log log n say then well they're still going to be there are actually very precise bounds known now but it's still more than polynomial but you know if so for content depth D you actually show it's exponential and the exponent itself varies depending upon exactly which D you select if you have log log n for D so it's slowly growing it drops down below exponential but it's still more than polynomial it's kind of in an intermediate zone and if D gets all the way up to log in over log log n so that's very near to log in but not quite there it's up above linear but still within polynomial so there's a kind of a trade off as you allow more depth the size can shrink that's all been pretty well worked out all right I don't know I maybe just one more slide see you know one thing that's key you know what one thing that came out of this is a very deep understanding of these very shallow circuits low depth circuits and this has some connection with I don't have skipping over this the bottom slide here but there are some connections with even infinitary objects so in so called infinite parody functions and infinite parody circuits which I may have countable or uncountable if you don't know how much you know mathematical logic you've seen but there's there's some nice connections with other branches of mathematics that have come out of that and I think the thing that's made me a little hopeful that this might have some bearing on PNP hasn't borne been borne out yet but not totally given up giving up hope on it it's conceivable is that you can express all searching problems in terms of depth to circuits which have so-called non-deterministic bits okay so I'm hoping that's something we've learned about depth to shallow low depth circuits may shed some light on this class NP all right so anyway that's all I want to say about P and NP but I thought idle do is since I let me branch out a little bit more broadly into in complexity theory tell you a little bit about what's been going on more recently because my history slide stopped in the 80s so in the 1990s I think for the most part question as an active area research basically people most people didn't have a good idea of how to tackle tackle that problem and complexity theory continued to be very fertile during that period but in other directions I just like to say a little bit about what people have so I think better good didn't miss me anyway I have a loud voice okay so I think you know sort of what the way I would sort of characterized work in the 1990s has been on exotic computational models what I mean by that so there's one kind of a model called an interactive proof system that was proposed about ten years ago and which has had a tremendous impact on the field if you haven't really dealt to I don't know how much you've seen of the NP if you have a good understanding of NP you feel so then maybe I can make some have you seen interactive proof systems know that okay let me try to give you a little flavor of what that is because you know in the case of NP say if you take a problem in NP like factoring in the sense of satisfiability maybe is a better example if i want to prove to you that a formula is satisfiable i just have to show you the satisfying assignment if i want to prove to you the formulas not satisfiable looks like I'm out of luck because I would have to walk through all possible assignments and show you that none of them work so that's the essence of NP is that membership is as it is easy to verify but this idea of an interactive proof system in a certain sense shows that that intuition or that feeling is not exactly right and let me give you an example of let me illustrate that there's a very nice exist people have worked on for a long time now another one this field is full of problems that people have worked on for a long time without success called the graph isomorphism problem graph isomorphism problem is you're given two graphs you know just point some lines to graphs and I want to know are they really the same graph that have been relabeled what talked about this morning great so presented as a kind of a language the way we do it in in complexity theory you know if I give you the two graphs means to the isomorphism problem is an NP problem because you can prove to me that the two graphs are isomorphic just by exhibiting which nodes match up with which notes then I can see that the edge it just go along correctly here with me so by just you have to just give me the mapping the isomorphism is what you tell me and then I can check that it works so the isomorphism problem is in NP whether it's in P whether you can test whether two graphs are isomorphic quickly not known how about to prove that two graphs are not isomorphic well that's not known to be an NP and itself would be a very big result if you could prove show that that was in NP the non isomorphism problem can you write down a short proof this is the reheat here's the set up you think of their being in an interactive proof system there are two parties there's approver so you guys the provers sort of thought of as being unlimited computationally so it's like a king with an army of slaves or graduate students undergraduate whatever and the king is you know limited didn't come that two graphs are not there's no way of matching of Ryu no of permuting one so that they will light one on top of another and are the same how do you prove that they're they really are different nobody knows but nonetheless there is a certain sense in which if you allow us to have a dialogue back and forth I can convince you that two graphs really are not isomorphic if in fact they aren't quickly so you have to understand here is the rules of the game let's flip it around you're going to convince me so the the the in this set up if I have my how am i doing timewise right okay cuz we're gonna this is my last slash nobility but by virtue of their big so many people in the army they are essentially unlimited and now imagine this king who has two graphs and he wants to know are they or are they not isomorphic now it's not enough for the king just to hand the problem to his slaves or her slaves and say you know what's the answer and be and you know hear about isomorphic and go home happy because the King knows the slaves are inherently lazy and the king not only wants to know the answer but it wants to be convinced of the answer he wants to be sure that they really did the work and they found out the right answer so if the graphs really are isomorphic we're in good shape because the slaves have a way of convincing the king that their rights of morphic how do they do that they show how it matches up they're you know they you know they have billions and billions of slaves they can work in they have to us you know slave over this and work it out but they can eventually find the way it matches up if in fact it does and they just show with the king now it matches up and the king is convinced but suppose they don't match up suppose the graphs are not isomorphic what are the slaves going to do because it's not an NP as far as we know we don't know what's an NP but there still is something they can do and they works like this is really cool what they're gonna engage in the following protocol the king is going to take the two graphs that's called an A and B it's going to turn his back and flip a coin secretly to pick one of the other at random say picked a okay then it's going to further flip some more coins to randomly rearrange a into a new graph see okay and then he sends C over to the slaves and says and asks did C come from a where did it come from B now think about that if this latest this ladies can determine that through a lot of work and if they can answer that question reliably so the kingdom maybe does this thing a hundred times if they can answer that question reliably it must have been the case that the two graphs were not isomorphic because if they had been if a and B really were isomorphic then C could have come from either one this ladies would have no way of knowing which was the source of C but if the graphs are not isomorphic then you can I tell because the slaves just have to go through the process of determining with the C is isomorphic to a or whether it's isomorphic to B and then they know which one it came from so they do this over and over again and if they always get the right answer the king is pretty convinced either that or the slaves are incredibly lucky but the king is pretty convinced that the two graphs had to be not isomorphic so this is a way of sort of generalizing the idea of NP to allow for this interaction and this randomness with a slow small probability of error but still you know kind of remarkably allows you to prove things have a certain property even though there's sort of not an NP so that's one exotic model the other exotic model is something you may have heard something about not going to say too much about it it's called a quantum computer and a quantum computer is something that exists in theory but maybe someday is actually something we might be able to build it's apparently doesn't violate any laws of physics and it says that if you could somehow store your bits down on the spin of electrons you know something really at a very very much more microscopic level than we're even doing today conceivably you can use quantum effects to somehow put your computer into a combination of also two different states simultaneously and in so doing have the computers sort of search through all of the many possibilities in brute-force through for search without having to try them at one after another it just sort of does them in parallel within the one physical device just by the magical quantum mechanics and so one of the result results that was shown not that long ago also guy who got that also got a prize Peter shor that for for example if you could really build a quantum computer then you could factor numbers in polynomial time even though in order don't know how to do that you know on a regular computer so let me just close with or getting back to P and NP I remember I gave this talk a few years back at Cornell and Hart Manus was there gave me the girl's letter in the first place and was my teacher as an undergraduate he has the question after my talk which was not that different from this talk he actually just said when which I think he meant was when is it going to be solved and I had a bet that I made with Len Adleman as an undergraduate as a graduate student excuse me we were graduate student together Berkeley in the 70s and we bet I bet that it would be solved by the end of the century and he bet that it would not be solved well I paid up my ounce of gold which was the value of the bet just last year so I don't know it's hard to predict when this problem is going to get solved I still am you know kind of hopeful but hard to say anyway that's my talk any question ya know the interaction person is not intended to be model physically just kind of like NPD really doesn't have exactly physical counterpart meaning not didn't well in there are many variants to interactive proof systems sort of the the garden-variety the most simplest one is the one I was kind of referring to where there's a verifier and approver the verifier is considered to be polynomial time limited sort of that's an a real computer but the prover is kind of considered to be unlimited computationally and that's the unrealistic and so that doesn't really have a physical counterpart however there are other variants that are concerned more in the cryptograph cryptography area where the prover is not considered to be uncommon limited it's just considered to be something has special information like a password and then you want the prove er to be able to convince the verifier that he has the password say which which sounds pretty trivial because could prove weakened to say well the password is you know pizza and that's the the password has been either then the verifier is convinced but it gets a little bit more subtle when you want the prover to convince the verifier that he knows the password without saying what the password is or even revealing an information about the password so that you can then you subsequently use the password multiple times and there are ways of doing that so there is a pretty big theory especially in the cryptography area where this thing does correspond to real buildable things but the complexity theory side not so much yes I think the prover and the verify the interactive proof systems are randomized protocols that's right what else yeah yeah they yeah you can assume that the slaves know how many randomized how much random information the King has access to yes you can assume that right but I'm not sure that that's going to help them at least in this case in other cases it might they still have to do isomorphism testing themselves and the only way to do that if you want to consider them to be physical devices would be through a brute force approach I see what you're saying so if he didn't he didn't move it too far from the original or in a sense interesting idea I don't know whether that might corrupt the protocol though if he was - he was - you know conservative about the amount of randomness he's using to move the thing around the protocol may not work anymore it may not be a convincing protocol to the king it seems to me that both using the interactive questioning or without it you're still only getting a statistical chance of being right yep I mean that's how the way works though you don't say they don't come back and say we didn't find anything because they could be that's not convincing to the king they could be lazy they could have been playing doing that that there's two millennia and you know and playing you know playing go or something useless but they could been just wasting their time you know and then they say well we worked hard we couldn't find thing but maybe there was something easy to find that they just didn't report but the protocol if you think about the protocol they described they're actually having to work hard and they convinced the King in the end the only way they can be getting the answer that they were getting would be for the graphs really to be not isomorphic unless they were extremely unlikely on the unless they were extremely lucky yeah okay all right the question is really I mean certainly the are you are you saying that you're not sure that the clock cycles are well spins no correlation you know it's see it's not yeah I'm trying to think the clearest way to answer your question I think the the the thing that the idea here is a little bit analogous to NP I mean if you're just going to restrict your attention to only buildable things even though our notion of NP is relevant I mean you there are some problems that take a long time to solve some problems take a short time to solve but the magic of NP is that there are some problems where it's easy even they may take a long time to solve they're short to verify and that's what this is similar I mean the non isomorphism it's short to verify in a somewhat different sense you can verify nine out and nine I mean if you want to you know if you'd say you don't completely trust your computer maybe it's you know it's has to be running for a long long time maybe it flipped a few bits along the way so it's just the fact that the computer gives you an answer maybe not something totally that you can trust but if you engage in this protocol all the computing that you need to do you can do yourself so it's completely convincing even beyond the faith that you would have to put into the computer that it's actually getting the right answer so that's not a great answer to the question it's really I think in the end it's ultimately kind of a mathematical characterization that's interesting here and maybe the mood not coming up with the best motivation in terms of you know practicality that I that it could but let me think about that mystically you can do the interactive one well doing what bloom I mean if you want to non determinacy check the graphs and not isomorphic that doesn't really help you beyond ordinary deterministic computation as far as we know so you're gonna have to still non-deterministically go through lots of different possibilities what is that machine good question you know I didn't pick that book I didn't pick that cover my publisher picked that cover though I think it's a very nice cover actually and I mean it is by you know it's by um DaVinci this picture and it's a it's um it's I mean I looked it up it's a it's a kind of a screw yeah you have to look if you look carefully you can figure out what it's doing the I'm trying to remember exactly you want to turn you want to remember there's something about maintaining a constant force on this screw but I can't so you're trying to change rotational this way too can't remember sorry I have to think about that but you know if you look you can actually sort of figure out what it's doing if you're looking you'll see this there's there are two sets of there's a set of teeth and a set of gear that the teeth of fitting into and as this thing is get being raised the teeth go further in so they're not turning as fast and they're the and the gear is getting larger that they're fitting into so somehow there's something that's balancing out there okay I can't remember now what the reasons the doing that is but it's there was a reason that it's not that hard to figure out I just not just not remembering it sorry well it let's see you know girdle was I think interested for whatever reason in whether mathematics or the work of a mathematician could be automated and he showed that the problem of testing and on you know problem testing whether something has a proof or not is undecidable unsolvable by computer and but if it was possible and it is decidable if you limit the number of limit the length now if it if it turned out that that was solvable quickly then in fact mathematics could be automated but if it took a long time then you sort of back it to where we were in the first place it's MIT it's now it's it's solvable but not in practice so the one hand is unsolvable you know in case of Salva but not in practice so it still remains sort of beyond beyond what you can do I remember I remember as a kid there was this these you know if you've seen any of these it was a serious bite on time life year old too young for this but the time life had a series of books on different subjects and they had one in mathematics which was fantastic if you can get ahold of that's the old thing now it's like 40 years old or so and I remember they had a picture of girdle in there was a strange-looking guy and he the caption was he's trying to determine if the human mind is a computer so presumably the guy who wrote the book must have gotten that somehow from girdle I guess and so that maybe gives a little bit of a clue as to how this fitting together he's philosophically speaking mathematically they were actually pretty different what am i doing right now I'm on leave what am i doing I'm actually that's I don't mean to be flip I'm actually I've gone back and forth working on P and NP and giving it a rest and you know writing a book and various things I'm actually lately have been seeing if I my last rest has been enough to get any new ideas which so far hasn't but so I'm actually been thinking about circuit complexity and such things for the past three months no news yet yes right to do that exactly the lis you can use the labeling to help you out but the general problem of testing where the two graphs are isomorphic well that would be great if you could solve one of that so that it's also like P and NP it's attracted a lot of people now not known to be np-complete it's one of the few problems that are sort of emo these problems that are np-complete if you solve any one of those quickly you solve all of NP quickly so those are sort of more hopeless in a sense but something like graph isomorphism is kind of in between seems to be anyway not known to be np-complete but not known to be in P but it wouldn't have such huge consequences if it went into P so it's more plausible that it would thank you okay thank you

Channel: Chao Xu

Views: 15,804

Rating: 4.8867927 out of 5

Keywords: googlevideo

Id: 3H0UxBF3kJg

Length: 73min 50sec (4430 seconds)

Published: Thu Nov 22 2012