1:43

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