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.