Now we're going to talk about P and NP, the two major classes of problems that form the basis for the theory of intractability. and so we've talked about search problems and what we're going to do is just name that class of problems and that's what we call NP. NP is the class of all search problems. now I just want to mention again that the classic definition that's often used in, in many books and papers that you'll read about this topic. the classic definition limits NP to yes/no problems. but again, the major conclusions that we draw are exactly the same. so, we just listed a bunch of problems that are in NP. And the way that we know is we had a very concrete definition of what we mean by a search problem. you have to be able to given a solution, you have to be able to verify in guaranteed polynomial time that you have a solution. and for satisfiability problems that we considered and factor all are in the class NP. so we, we're using the concept of a search problem to classify some problems. One way to think of NP is it's, it's really what we would like to be able to compute. We'd like to have algorithms that solve all of these problems. and it's a very, very general class of problems that's like, it's almost articulating in as general way as possible what we mean by a problem that we want to solve computationally. So, these are the problems that we'd like to solve. Some of them we can, we know how to solve, some of them we don't. that's the NP. now, by contrast, there is another class P where we add a, a restriction and that's the class of search problems that we know how to solve in polynomial time. So, that is we have, generally we have we prove that problems in P by demonstrating an algorithm that is guaranteed to run in polynomial time for any instance of that problem. And again, the classic definition is about yes/no problems. so here's bunch of problems that are in P. and so we already showed L solve cuz Gaussian elimination runs in polynomial time. And we already talked about LP cuz algorithm works for linear program, programming. and then pretty much all the algorithms that we've covered in this course like are cast as search problems. And also can, have polynomial time solutions. We've been talking about programs that are polynomial time solutions and just a little bit has to be done to convince yourself that, or to cast the problem as a search problem that many of them are explicit as search problems, like ST connectivity. You're searching for a path in a graph you know, and, and Theseus and the minotaur, you know, showed if you, if you are given a path, you can check that it's a path easily. So, it's a search problem. so P is the class of search problems that can be solvable in polynomial time. so the significance of p is, those are the ones that we actually do compute feasibly. So, NP's the ones, all the ones we would like to, and P is all the ones that we actually do compute feasibly. and those are perfectly well defined classes of problems. now, what is the N and NP for? Well, just the, a brief moment to talk about that. the N and NP stands for non-determinism. and the idea of a non-deterministic machine is one that can guess the desired solution. and that's an abstract machine. as far as we know, we don't have non-determinism in real life devices. but in, but it's fine to have an abstract machine of that sort. Remember, for our implementation for regular expression pattern matching, the way that we solved that practical problem was to image a non-deterministic machine. And then, write a program that would simulate that machine by trying all different possibilities. and, in fact, that whole exercise really gets at the difference between polynomial exponential time. first approach is the naive approach to simulating that machine turns out to be an algorithm that can run in exponential time for some inputs. And we actually saw that today there's implementations like that out there that hackers can exploit to deny service. The implementation we show had guaranteed polynomial time. So, non-determinism was an abstract device that we used to help us try to get to a real practical solution and that's what we're doing again. So, let's imagine, we have a non-deterministic machine that can guess the solution. so like if you're in, in a deterministic machine, if you make a, an array and create an array of size n, then it, Java we know deterministically, initializes the entries to all zero. but what if that array A is supposed to be our solution to a integer linear programming problem? we could have a non-deterministic machine initialize the entries to the solution. They could just guess what the right answer is and initialize it. So, it seems like a really, really powerful capability. so for example, for integer linear programming, we could just tell the non-deterministic machine guess the solution and we'd be done. and the same concept goes all the way down to a touring machine. the whole idea of the finite state machine or of any computation that people think about is the machine's in some state, and it's fully determined what the next state will be. And Turing machine's the simplest type of imaginary machine with that kind of capability. But it's very simple to make a Turing machine non-deterministic, the same way that we made Finite Automata non-deterministic. You just let it go to more than one possible state. So, when you think about non-determinism in this way, it is pretty clear almost immediately that NP is a class of search problems that are solvable in polynomial time on a non-deterministic Turing machine. Even, if the machine gives the solution, what we requiring is that we have to be able to check that there is a solution in polynomial time. and that's, that's NP. So, what we have led to immediately is the, what's called the extended Church-Turing thesis. and that's the idea that P is, is the ones that we know how to solve, but it's the class of the problems that we ever going to be able to solve in the, in the natural world. and again evidence were supporting the thesis is that all the computers that we know about were simulating in polynomial time. people wondered, have wondered and still wonder, is it possible that there are computers out there that work differently or more efficiently than the computers that we built. here's the an interesting and simple example. there's a thing called a Steiner tree, which is like an MST, except you're not restricted to have your lines go through the points that are given. Steiner tree you're given some points. And what you're supposed to do is find a set of lines of minimal length that connect the end points. Now, this is quite a bit of math and geometry even to prove that a given set of lines is a Steiner tree. But like for four points it's known like this, in a rectangle or array. that's what the Steiner tree looks like. Can we write a program to compute Steiner trees? it's a search problem. And although that it's not, not completely easy to characterize as a search problem, but it is. But anyway, the point for now is that people wondered actually if you put soap in between two glasses, the film formed by the soap or soap bubbles is another way to think about it. But this is a two, making it two-dimensional if you put four points and put soap and people have done this experiment, that's a photo off the, off the web, you get a Steiner tree. and, you know, who knows what kind of computation is involved to make that. if you put lots of points, people have done I, I, I don't know what number. but they can get Steiner trees for substantial numbers of points. can we really compute Steiner trees that way? Well, you can construct things where it doesn't actually get the actual Steiner tree. So, it doesn't really work. and that's just one example of an attempt. there's plenty other examples out there. but the Chur, extended Church-Turing thesis hasn't been with us for as long as the Church Turing thesis and maybe it's not quite as strong, but it's held for quite a, quite a long time. and people are assuming that there's not going to be a design that's going to make the differ ence between polynomial time in this natural world. if we're going to make future computers more efficient, we're just going to improve our existing designs. that's the extended church term thesis. but it leaves us with all of this leads us with a basic question. Does P equal NP? so P is all the problems we can solve in the natural world, and P is all the search problems that would like to solve. if we had non-determinism in the natural world do we have non-determinism in the natural world? Does non-determinism help? that's the question. Does P equals NP? this question has been around for a long time and has even made it into the popular culture. and I think it'll make it into the popular culture much more when we start having because we're starting to have massive online courses where many more people are learning about these fabulous concepts. now here's another way to think about P versus NP. it's the like idea of automating creativity. it's one thing to be creative, it's another thing to appreciate creativity. so Mozart comes up with music, a piece of music. Once that thing is created, we can appreciate it. Or Andrew Wiles proved with his last theorem and however he came up with it, there's a way to check it, somebody can check it. or a, somebody designs an, an air, air foiler or airplane wing, we can verify that it has the properties it's suppose to. or Einstein proposes a theory, somebody can validate it. So, there's the creative let's, let's, let's make something or, or come up with something, that's the analog to that is a solution to a problem, a search problem. and the ordinary thing to do is to check it. but if P equals NP, there's no difference. we can, we, it's really like automating creativity. that's the computational an analog to P equals NP question is the computational analog to automating creativity. Is P equals NP? That's the central question. , can you always avoid before searching and do better? for search problems, since we have a small solution that can be checked in palonomial time, ther e's always a exponential time solution, which is try all possible solutions. but that's not, the question is, can you can you always do better than that? That's the, the, the essence of the P equals NP question. so there's two possibilities. If P, if P is not, if P is a search problem so it's certainly an NP. Any problem in NP is also in P. so, the question is are there some problems, some search problems that we can't solve in polynomial time? so if the answer to the question is yes, then all the problems that I've mentioned that nobody knows the solution to despite people working on them for many decades. if P is equal to NP there's polynomial times out, algorithms for those out there, we just haven't found them yet. if the answer to that is no, if that that's really something fundamental about our universe that, that something, said something profound about the power of non-determinism, non-determinism. If, if P equals NP, non-determinism actually doesn't help, not equal NP. it would, now, the overwhelming consensus is that P equals, not equal to NP. and we'll talk some more about some reasons that people believe that. but when thinking about it and you can really convince yourself that it really seems as though having a machine. And a machine that can when you initialize a ray, an array, initialize it with a solution to a integer linear programming problem really would seem that a machine like that is going to be more powerful than the machines that we're using. and that's why people believe that P is not equal to NP. But the frustrating thing is that, theoretical computer scientist, and mathematicians have been working on this for many, many years and no one has been able to prove it. actually there's the Millenium Prize. you can earn a million dollars from Clay Mathematics Institute if you resolve PNP. Equals NP. actually there's other math problems on that list and but people who know algorithms. First of all, you could learn, earn way more than a million dollars if, if you resolve this problem. second of all, if you're expert in algorithms, there's lots of other ways to earn a million dollars. so it's not about the million dollars, it's about this is some would argue one of the most important open mathematical questions that faces us right now.