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.