0:00

So I hope that pretty much all of you had heard about the P vs NP question.

Before you enrolled in this class. But if you haven't, you can pretty much

guess what that question is. I've defined for you, both of these

classes of problems. P is the class of problems that are

polynomial times solvable Solvable. Whereas the problems in NP have the

property that, at least given the solution, you can quickly verify that it

is, indeed a correct solution. It's why the conjecture that P is not

equal to NP, that is, merely the ability to efficiently verify purported

solutions, is not sufficient, to guarantee Polynomial time solvability.

Indeed, Edmonds, back in 1965, before we even had the vocabulary NP, remember that

came along only in '71. Edmonds already in '65, was, essentially

conjecturing that P is not equal to NP. In the, form that he was conjecturing,

there's no polynomial time algorithm, that solved the traveling salesman

problem. But let me emphasize we genuinely do not

know the answer to this question, there is no proof of this conjecture.

P vs NP question is arguably the open question in computer science, it's also

certainly one of the most important and deep, deepest open questions in all of

mathematics. For example, in 2000 The Clay mathematics

Institute published a list of 7 millennium.

prize problems. The P vs NP question, is 1 of those 7

problems. All of these problems, are extremely

difficult, and extremely important. The only one that's been solved to date,

is the [UNKNOWN] conjecture. The Remount hypothesis, is another

example, on that list. And they're not called the millennium

prize problems for nothing, if you solve 1 of these mathematical problems, you get

a cash prize of 1 million dollars. Now, while a million dollars is obviously

nothing to sneeze at, I think it sort of understates the importance of a

mathematical question like P versus NP, and the advance in our knowledge that a

solution to the question would provide, I think, would be much more significant

than a price check. So how come so many people thing that P

is not equal to NP, rather than the opposite, P=NP? Well, I think the

dominant reason is sort of a psychological reason, namely that if it

were the case that P=NP, then all you'd have to do, remember, is exhibit a

polynomial time algorithm for just 1, np complete problem.

And there are tons of np complete problems.

And a lot of extremely smart people, have had np complete problems that they've

really cared about, and either on purpose or accidentally, they've been trying to

develop efficent algorithms for them. Noone has ever succeeded in over 1/2

century of serious computational work. The second reason is sort of

philosophical, P=NP just doesn't seem to jive with the

way the world works. Think about it, for example, when you do

a homework problem in a class like this one.

And consider 2 different tasks. The first task is I give you question,

and I asked you to come up with a correct solution, say a proof of some

mathematical statement. The second task would be just grade

somebody else's suggest proof. Well, generally it's a lot harder to come

up with the correct argument from scratch,

compared to just, verifying a correct solution, provided by, somebody else.

And yet, P equals NP would be saying, that these two tasks, have exactly the

same complexity. It's just as easy, to solve homework

problems, as it is, to just read, and verify, the correct solution.

So I don't know about you, but it's always seemed to me to be be a lot harder

to come up with a mathematical argument from scratch as opposed to simply grading

somebody else's solution. So now it seems to require a degree of

creativity, to pluck out from this exponentially big space of proofs, a

correct one for the statement at hand. Yet, P = NP would suggest that, that

creativity could be efficiently automated.

But of course, you know, P versus NP being a mathematical question.

We'd really like some mathematical evidence, of which way it goes.

For example, if P is not = N P. And here we really know shockingly

little. There just isn't that much concrete

evidence at this point, that, for example, P is not = to NP.

Now, maybe it seems bizarre to you, that we're struggling to prove that P is not

equal to NP. Maybe it just seems sort of obvious that

there is no way that you can always construct proofs, in time, polynomial, in

what you need to verify proofs. But, the reason this is so hard to prove

mathematically, is because of the insane richness of the space of polynomial time

algorithms. And indeed, it's this richness that we've

been exploiting all along in these design and analyses of algorithms classes.

Think for example about matrix multiplication.

Had I not shown you Strauss's algorithm, I probably could have convinced you more

or less, that there was no way to solve matrix multiplication faster than cubic

time. You just look at the definition of the

problem and it seems like you have to do cubic work.

Yet, Strauss's algorithm and other follow ups show you can do.

Fundamentally better, than, the naive cubic running time algorithm, for matrix

multiplication. So there really are, some quite

counter-intuitive, and hard to discover, unusually efficient algorithms, within

the landscape of polynomial time solutions.

And who's to say that there aren't some, more exotic species, in this landscape of

polynomial time solvability, that have yet to be discovered, which can make.

In-roads even on empty complete problems. At this point, we really don't know.

At the very least our currently primitive understanding of the fauna within the

complexity class P, is an intimidating obstruction to a proof that P is not

equal to NP. I should also mention that, as an

interesting counterpoint to Edman's Conjecture in '65, was a conjecture by

Gödel. This is the same logician Kurt Gödel,

Gödel's completeness and incompleteness theorems.

He wrote a letter to John von Neumann in 1956, where he actually conjectured the

opposite, the P is = to NP,so who knows.

So I've tried to highlight for you, the most important things that an algorithm

designer, and serious programmer should know, about NP problems, and NP

completeness. One thing I haven't explained, which you

might be wondering about, is, what on earth does NP stand for anyways?.

A common guess would be not polynomial but this is not what it stands for.

The answer's going to be a little bit more obscured in deed it's a bit of an

acronym-ism nondeterministic polynomial So this is referring to a different but

mathematically equivalent way to define the complexity class NP in terms of an

abstract machine model known as nondeterministic turing machines.

But, generally, for some of those thinking about algorithms, generally for

the programmer I would advise against, thinking about problems in NP, in terms

of this original definition, with this abstract machine model.

And I'd instead, strongly encourage you, to think about the definition I gave you,

in terms of the efficient recognition, the efficient verification, of purported

solutions. Again, they're mathematically equivalent,

and I think, efficient verification makes more sense It's in the algorithm design.

Maybe you're thinking that N P is a perhaps not that good, and somewhat

inscrutable definition for what's a super important concept.

But it's not for lack of discussion and effort on the communities part.

So very soon after the work of Cook and Carp, it was clear to everyone working in

the west on algorithms and computation that this was a super important concept,

and people needed to straighten up their vocabulary asap.

Don Knuth ran a poll amongst members of the community.

He reported on the results in his SIGACT news article from 1974, "A Terminological

Proposal," and NP Completeness was the winner, and that was then adopted in the

landmark book "Design and Analysis of Algorithms" by Hopcroft and Ullman,

and that's the way it's been ever since. There is one suggestion that was passed

over, which I find quite amusing, let me tell you about Suggestion was pet PET.

So, what is PET acronym for? Well, it's flexible so initially the interpretation

would be possible exponential time. In problem.

Now suppose its some day people prove that P is not equal to NP, then the

meaning would change to provably exponential time.

So now its not the time to nit pick with the suggestion that you could prove P not

equal to NP without actually proving an exponential lower bound merely a super

polynomial bound. Lets leave objects like that of side and

ask what would happen if P actually turned out to be equal to NP, well then,

you could call PET previously exponential time problems.

But of course, at this point PET is nothing more than an amusing historical

footnote. NP-complete is the phrase that you got to

know.