0:03

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.

Â