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.

NP-Completeness

Algorithms, Part II

Meet the Instructors