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

Â