Now we're going to look at MP completeness, which is, another idea that gives us even, even stronger, evidence that the problems that we can reduce that to are difficult. and MP completeness is a simple idea. it sounds almost, crazy. It's, asking for a lot. an MP problem is MP complete if every single problem in MP polynomial time reduces to that problem. that sounds like a fairly abstract concept, but in 1970's, right about the time Ed Karp was working Cook proved, just before actually Cook proved, and later Levine, a few years later, independently that sat is MP complete. so every problem in NP polynomial time reduces to sat. Hm. Well, that has profound implications that I'll talk about on the next slide. But first let's take a look at the Cook Levin theorem. Mm, this is an extremely brief proof sketch, but the idea of the theorem is. I can, I can describe the idea of the theorem. The execution of it is a tour de force in both cases, but the idea I can describe. the, so, a problem in NP. NNP is one that can be solved in polynominal time by a non-determinate Turing machine. Well, what's a non-determinate Turing machine exactly? Well, it's just a set of states and symbols and, if you in a table basically that says if you have a certain symbols or a certain state, you go to another table. Out of state. so actually, and actually at the beginning the way mathematicians thought of turing machines was not with diagrams but just as topals, as a list of every state, it's a list of other states and symbols and things, just following certain rules. so description of a Turing machine is a formal description of a bunch of rules with logically saying what happens and, and there's not much that happens. if you're in a state and you see a symbol, go to another state, move the tape head, and so forth. simple formal rules. so what Cook found was that, so anything that you can compute in, with a non-deterministic Turing machine, anything that you can compute you can write down on non deterministic turing machine for, and what Co okay found was a way to encode a non deterministic turing machine as an instance of SAT and so what does that mean. It's just writing down what a Turing machine is in kind of a different notation as an instance of SAT. What does that imply? Well if you could solve that instance of sat in polynomial time. you're simulating operation of that Turing machine. and you could solve, the computation that Turing machine's trying to do in polynomial time. That's the sketch of, the Cook-Levin theorem. anything that you can compute in a, on a non-deterministic Turing Machine in polynomial time. you can write as a SAT instance that you could solve in polynomial time. if you could solve the SAT instance quickly, you could do the non deterministic Turing Machine computation quickly. So any problem in NP, polynomial time reduces to SAT. That's the, Cook-Levin theorem. And if you combine that which was done immediately with Karp's observation, well first of all it means that, that there's a polynomial time algorithm for SAT, if and only if P equals NP. so that is non-determined, only if it's non-determined, doesn't help. You have the polynomial time algorithm for SAT. because polynomial time algorithm for SAT immediately means you could solve, all problems, in NP in polynomial time. That's what, that's what Cook's Theorem's about. so, and NP completes getting into the popular culture, as well. but what is the implications? It's means all of these thousands and thousands of problems all of a sudden reduce to SAT. and that means they're all equivalent. they're all manifestations of the, of the same problem. if you could solve any one of these problems in polynomial time, then it means that you can solve them all in polynomial time. That's a very profound result. particularly because thousands and thousands and thousands of important scientific problems, all the problems that we aspire to compute with feasible, feasible algorithms, they're all in the same class. if we could solve any one of them in polynomial time, we could solve all of them in polynomial time. so, what are the implications of MP completeness? So, it's the idea that SAT captures the difficulty of the whole class, NP. and if, either way, if you can prove that there's some problem, in NP, that there's no polynomial time algorithm for, then it's not going to be first half. And the other thing as I mentioned you can replace SAT with any problem that has been reduced down from SAT. Not just Karp's problems, but any of the thousands. so, so now, nowadays proving a problem in p-complete was actually many examples where it's actually guided what scientists do because it is saying something profound about the, profoundly important about the problem. so here's an example. I. I'm getting to that Ising spin model that I referred to. it was introduced in the'20s and people liked the model and they wanted to apply it and trying to compute with it but it's one thing to have a model, it's another thing to apply the model, try to say something about the real world that might involve some computation. so in the'40s a mathematical solution was found tour de force paper, which is fine, but in the real world it's 3D and a lot of smart people looked for. 3D solution to this problem. turns out to be In 2000 it was proven to be MP complete. And people work for 50 years trying to solve this problem. and . now we understand why they were unsuccessful. Because if they had been successful it would imply that, all those, all those other problems are going to be running in polynomial time. Or it would imply that PNP. Equals NP, and nobody believes that PNP. Equals NP. . So here we are. We're still with this, overwhelming consensus that P is not equal to MP. and not only that if P is not equal to MP, then MP complete problems are some other subset, of MP, and there's as I mentioned a zoo of complexity classes, at the, end of the reduction lecture a lot of them are, starting from this diagram, you can come up with, many, many other ideas to try to get at it and there's not a lot of problems that people ev en have any kind of conjecture for falling outside. Even though it seems like obvious there ought to be lots of problems in MP that are not in. It's quite a frustrating situation for people working in the field. So the right hand diagram's simple. The left hand diagram gets more and more complicated as people work on it. But really, the fundamental reason that we believe that p equals, not equals MP, gets back to that creativity. And I'd like to read a quote from Avi Gregerson, who have at the Institute for Advance Science here in Princeton, We admire Wiles' proof of Fermat's last theorem, and the scientific theories of Newton, Einstein, Darwin, Watson and Crick. The design of the Golden Gate Bridge and the Pyramids, precisely because they seem to require a leap which cannot be made by everyone, let alone by a simple mechanical device. It's all about, it's a lot more difficult to create something than to check that it's good. So here's the summary P's the class of search problems that are solvable in polynomial time. Np's the class of all search problems and some of which seem pretty hard and people have tried really hard to work on'em. NP complete in a sense are the, the hardest problems in NP'cause you know, all the problems in NP reduce to those problems. we talk about a problem having no polynomial prime algorithm, that is intractable, er, you know. And. we know that, lots and lots of fundamental problems are NP complete. so what we want to do is use theory as a guide, when we're confronting problems. everyone has to realize that a polynomial time for algorithm for an NP complete problem would be a stunning. Scientific breakthrough win a million dollars in this video thinks he can do it. certainly you will confront NP complete problems sometimes there's thousands and thousands and thousand of them out there. and probably a good idea, safe bet is to assume that P is not equal to NP because almost everyone believes that and therefore that there is NP comply problems are very intractable. You're not going to be able to guarantee polynomial running time for an algorithm. So, you better know about those situations and proceed accordingly. And, and we'll look at a couple of things to do. around in the 1980s came to Princeton to start their computer science department and we built this building. And they asked you know, a lot of the buildings there, nobody asked. A lot of the buildings at Princeton have gargoyles, and I wanted to have something on our building that could stand the test of time, and this is what we wound up with, in a pattern on the brick up on the top of the building. Now I could just leave that there and maybe these count, the solution will get edited out. And so the, you can work on figuring out what that means. But, you know, anyway, here's the solution. the indented bricks are ones. I mean, ones that aren't indented are zeros in this little pattern. and they're just asking. encoding. So the top row is asking for P. and then the second one is asking for equal and then N. and then another P. and then, a question mark. so it seemed to me like that pattern, would span the test of time and that was that was over 25 years ago. now if, everyone asks, what do you do, if somebody proves that in fact P equals NP. Well in that case we can put an exclamation point on there. If somebody proves that P is not equivalent P then we're going to have to remove a lot of bricks. that's an, an introduction to the theory of intractability.