Now we're going to talk about P and NP, the two major classes of problems that
form the basis for the theory of intractability. and so we've talked about
search problems and what we're going to do is just name that class of problems and
that's what we call NP. NP is the class of all search problems. now I just want to
mention again that the classic definition that's often used in, in many books and
papers that you'll read about this topic. the classic definition limits NP to yes/no
problems. but again, the major conclusions that we draw are exactly the same. so, we
just listed a bunch of problems that are in NP. And the way that we know is we had
a very concrete definition of what we mean by a search problem. you have to be able
to given a solution, you have to be able to verify in guaranteed polynomial time
that you have a solution. and for satisfiability problems that we considered
and factor all are in the class NP. so we, we're using the concept of a search
problem to classify some problems. One way to think of NP is it's, it's really what
we would like to be able to compute. We'd like to have algorithms that solve all of
these problems. and it's a very, very general class of problems that's like,
it's almost articulating in as general way as possible what we mean by a problem that
we want to solve computationally. So, these are the problems that we'd like to
solve. Some of them we can, we know how to solve, some of them we don't. that's the
NP. now, by contrast, there is another class P where we add a, a restriction and
that's the class of search problems that we know how to solve in polynomial time.
So, that is we have, generally we have we prove that problems in P by demonstrating
an algorithm that is guaranteed to run in polynomial time for any instance of that
problem. And again, the classic definition is about yes/no problems. so here's bunch
of problems that are in P. and so we already showed L solve cuz Gaussian
elimination runs in polynomial time. And we already talked about LP cuz algorithm
works for linear program, programming. and then pretty much all the algorithms that
we've covered in this course like are cast as search problems. And also can, have
polynomial time solutions. We've been talking about programs that are polynomial
time solutions and just a little bit has to be done to convince yourself that, or
to cast the problem as a search problem that many of them are explicit as search
problems, like ST connectivity. You're searching for a path in a graph you know,
and, and Theseus and the minotaur, you know, showed if you, if you are given a
path, you can check that it's a path easily. So, it's a search problem. so P is
the class of search problems that can be solvable in polynomial time. so the
significance of p is, those are the ones that we actually do compute feasibly. So,
NP's the ones, all the ones we would like to, and P is all the ones that we actually
do compute feasibly. and those are perfectly well defined classes of
problems. now, what is the N and NP for? Well, just the, a brief moment to talk
about that. the N and NP stands for non-determinism. and the idea of a
non-deterministic machine is one that can guess the desired solution. and that's an
abstract machine. as far as we know, we don't have non-determinism in real life
devices. but in, but it's fine to have an abstract machine of that sort. Remember,
for our implementation for regular expression pattern matching, the way that
we solved that practical problem was to image a non-deterministic machine. And
then, write a program that would simulate that machine by trying all different
possibilities. and, in fact, that whole exercise really gets at the difference
between polynomial exponential time. first approach is the naive approach to
simulating that machine turns out to be an algorithm that can run in exponential time
for some inputs. And we actually saw that today there's implementations like that
out there that hackers can exploit to deny service. The implementation we show had
guaranteed polynomial time. So, non-determinism was an abstract device
that we used to help us try to get to a real practical solution and that's what
we're doing again. So, let's imagine, we have a non-deterministic machine that can
guess the solution. so like if you're in, in a deterministic machine, if you make a,
an array and create an array of size n, then it, Java we know deterministically,
initializes the entries to all zero. but what if that array A is supposed to be our
solution to a integer linear programming problem? we could have a non-deterministic
machine initialize the entries to the solution. They could just guess what the
right answer is and initialize it. So, it seems like a really, really powerful
capability. so for example, for integer linear programming, we could just tell the
non-deterministic machine guess the solution and we'd be done. and the same
concept goes all the way down to a touring machine. the whole idea of the finite
state machine or of any computation that people think about is the machine's in
some state, and it's fully determined what the next state will be. And Turing
machine's the simplest type of imaginary machine with that kind of capability. But
it's very simple to make a Turing machine non-deterministic, the same way that we
made Finite Automata non-deterministic. You just let it go to more than one
possible state. So, when you think about non-determinism in this way, it is pretty
clear almost immediately that NP is a class of search problems that are solvable
in polynomial time on a non-deterministic Turing machine. Even, if the machine gives
the solution, what we requiring is that we have to be able to check that there is a
solution in polynomial time. and that's, that's NP. So, what we have led to
immediately is the, what's called the extended Church-Turing thesis. and that's
the idea that P is, is the ones that we know how to solve, but it's the class of
the problems that we ever going to be able to solve in the, in the natural world. and
again evidence were supporting the thesis is that all the computers that we know
about were simulating in polynomial time. people wondered, have wondered and still
wonder, is it possible that there are computers out there that work differently
or more efficiently than the computers that we built. here's the an interesting
and simple example. there's a thing called a Steiner tree, which is like an MST,
except you're not restricted to have your lines go through the points that are
given. Steiner tree you're given some points. And what you're supposed to do is
find a set of lines of minimal length that connect the end points. Now, this is quite
a bit of math and geometry even to prove that a given set of lines is a Steiner
tree. But like for four points it's known like this, in a rectangle or array. that's
what the Steiner tree looks like. Can we write a program to compute Steiner trees?
it's a search problem. And although that it's not, not completely easy to
characterize as a search problem, but it is. But anyway, the point for now is that
people wondered actually if you put soap in between two glasses, the film formed by
the soap or soap bubbles is another way to think about it. But this is a two, making
it two-dimensional if you put four points and put soap and people have done this
experiment, that's a photo off the, off the web, you get a Steiner tree. and, you
know, who knows what kind of computation is involved to make that. if you put lots
of points, people have done I, I, I don't know what number. but they can get Steiner
trees for substantial numbers of points. can we really compute Steiner trees that
way? Well, you can construct things where it doesn't actually get the actual Steiner
tree. So, it doesn't really work. and that's just one example of an attempt.
there's plenty other examples out there. but the Chur, extended Church-Turing
thesis hasn't been with us for as long as the Church Turing thesis and maybe it's
not quite as strong, but it's held for quite a, quite a long time. and people are
assuming that there's not going to be a design that's going to make the differ
ence between polynomial time in this natural world. if we're going to make
future computers more efficient, we're just going to improve our existing
designs. that's the extended church term thesis. but it leaves us with all of this
leads us with a basic question. Does P equal NP? so P is all the problems we can
solve in the natural world, and P is all the search problems that would like to
solve. if we had non-determinism in the natural world do we have non-determinism
in the natural world? Does non-determinism help? that's the question. Does P equals
NP? this question has been around for a long time and has even made it into the
popular culture. and I think it'll make it into the popular culture much more when we
start having because we're starting to have massive online courses where many
more people are learning about these fabulous concepts. now here's another way
to think about P versus NP. it's the like idea of automating creativity. it's one
thing to be creative, it's another thing to appreciate creativity. so Mozart comes
up with music, a piece of music. Once that thing is created, we can appreciate it. Or
Andrew Wiles proved with his last theorem and however he came up with it, there's a
way to check it, somebody can check it. or a, somebody designs an, an air, air foiler
or airplane wing, we can verify that it has the properties it's suppose to. or
Einstein proposes a theory, somebody can validate it. So, there's the creative
let's, let's, let's make something or, or come up with something, that's the analog
to that is a solution to a problem, a search problem. and the ordinary thing to
do is to check it. but if P equals NP, there's no difference. we can, we, it's
really like automating creativity. that's the computational an analog to P equals NP
question is the computational analog to automating creativity. Is P equals NP?
That's the central question. , can you always avoid before searching and do
better? for search problems, since we have a small solution that can be checked in
palonomial time, ther e's always a exponential time solution, which is try
all possible solutions. but that's not, the question is, can you can you always do
better than that? That's the, the, the essence of the P equals NP question. so
there's two possibilities. If P, if P is not, if P is a search problem so it's
certainly an NP. Any problem in NP is also in P. so, the question is are there some
problems, some search problems that we can't solve in polynomial time? so if the
answer to the question is yes, then all the problems that I've mentioned that
nobody knows the solution to despite people working on them for many decades.
if P is equal to NP there's polynomial times out, algorithms for those out there,
we just haven't found them yet. if the answer to that is no, if that that's
really something fundamental about our universe that, that something, said
something profound about the power of non-determinism, non-determinism. If, if P
equals NP, non-determinism actually doesn't help, not equal NP. it would, now,
the overwhelming consensus is that P equals, not equal to NP. and we'll talk
some more about some reasons that people believe that. but when thinking about it
and you can really convince yourself that it really seems as though having a
machine. And a machine that can when you initialize a ray, an array, initialize it
with a solution to a integer linear programming problem really would seem that
a machine like that is going to be more powerful than the machines that we're
using. and that's why people believe that P is not equal to NP. But the frustrating
thing is that, theoretical computer scientist, and mathematicians have been
working on this for many, many years and no one has been able to prove it. actually
there's the Millenium Prize. you can earn a million dollars from Clay Mathematics
Institute if you resolve PNP. Equals NP. actually there's other math
problems on that list and but people who know algorithms. First of all, you could
learn, earn way more than a million dollars if, if you resolve this problem.
second of all, if you're expert in algorithms, there's lots of other ways to
earn a million dollars. so it's not about the million dollars, it's about this is
some would argue one of the most important open mathematical questions that faces us
right now.