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.