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.