▶︎ 0:00 Let me remind you where we left off the last episode. We were talking about how the map application on your phone computes driving directions, and that led us to talk about Dijkstra's algorithm, an efficient method for computing a shortest path from one point to another. And along the way, we also observed that what's remarkable about that is there's potentially an astronomical number of options for what the shortest path between two points could be. And Dijkstra's algorithm somehow cleverly sifts through that ridiculous number of solutions to very quickly hone in on the right answer.
▶︎ 0:32 Let me just remind you of the network that we looked at that showed you why the number of routes can blow up exponentially very, very quickly as the network gets large. Remember we were thinking about going from point A to point B, and we were just imagining that there were four independent decisions to make. So you can take the northern route or the southern route, and four times in a row, you decide which of the two you want to do. And then we were thinking of the travel times looking like this. And we observed that it's not hard to see that what you want to do is alternate the northern and southern routes to get to the destination as quickly as possible.
▶︎ 1:19 So it wasn't a difficult problem. We didn't have to think hard to figure out what we wanted to do. But remember, we did observe that we're doing something clever. We're doing a shortcut. We're not actually doing exhaustive search. We're not taking the two times two times two times two, or 16 different routes, and then comparing them individually. We're using a shortcut. We say, "Oh, well, we should just do the best thing in each stage."
▶︎ 1:42 Now, in a more complex network, like the ones that we drive through every day, it's not obvious it's so simple to figure out this shortcut to see what the best route is, but that's exactly what Dijkstra's algorithm accomplishes. And we also talked about that if you didn't have things like Dijkstra's algorithm for computing shortest paths, if you didn't have ways to take advantage of this algorithmic shortcut and sift through all these options, literally you would not be able to compute the shortest path from point A to point B in reasonably large networks.
▶︎ 2:13 Remember, we even said that if you just chain 265 of these things in a row, all of a sudden the number of options is literally ballpark the estimated number of atoms in the known universe. And 265, that's not, if you're driving to your relatives' like several states over, it's a comparably complex shortest path problem. So that's great. Shortest paths, tons of options, doesn't matter. We don't look at them all. We just very quickly hone in on the best option.
▶︎ 2:43 Can we always do that? Are there always such algorithmic shortcuts? In a way, we know that we have the halting problem, so some problems have no algorithm at all. But you say, but for the types of problems we see in day-to-day life? Just in regular living? Could it be that there's always these algorithmic shortcuts, or are we ever stuck actually trying to examine all of the possible options?
▶︎ 3:06 We talked about John von Neumann earlier in the series. That was back when we were talking about the first attempts to really realize general-purpose computing devices. And von Neumann, he was a very quotable person. One of his quotes, which I don't totally agree with, but there's a grain of truth to it, is, "In mathematics, you don't understand things. You just get used to them." I don't totally agree. I do think you feel your understanding deepening as you study more and more mathematics, but then there is always this stuff where you're like, "Eh, it's just how it works." And you just get used to it.
▶︎ 3:45 And so for people who think about computation and who think about algorithms, one of those things you have to get used to is that seemingly very minor modifications to a problem statement, so very small changes in the computational task you're trying to carry out can have a dramatic effect on how quickly you're going to be able to solve the problem.
▶︎ 4:08 For example, let's take the same shortest path problem, and let's tweak it just a little bit. Let's tweak it so that I don't just want a shortest path from point A to point B, but I also want to visit every other intersection on the way. This example is not a good one, because to go from point A to point B, you have no choice but to visit everything else on the way. But imagine this was part of some bigger network. Imagine there's this bigger network maybe that has 100 intersections as part of it, and I still want to get from point A to point B, but I would like to visit all other 100 points en route.
▶︎ 4:48 Imagine, for example, you take your kids to an amusement park and they insist on trying every ride at the amusement park once. That means you gotta travel around the amusement park hitting every place exactly once, and you would like to do that as quickly as possible. That's a variance of the shortest path problem, and it's a famous problem. It's a problem known as the traveling salesman problem, or the TSP. TSP, traveling salesperson problem.
▶︎ 5:17 This is a super famous example. I mentioned that people like George Dantzig were having so much success tackling all kinds of different problems. And yet somehow, back in the golden age of algorithms in the '40s and '50s and '60s, the traveling salesperson problem, or the TSP, that was one of those problems that just stubbornly seemed to resist any efficient solution, even though the brightest minds at the time were working hard on finding one.
▶︎ 5:43 This traveling salesperson problem, or the TSP, it shares a number of features with the shortest path problem, which at this point we know and love. First of all, in principle, like with shortest paths, in principle, you could solve the TSP through exhaustive search. You start at point A, there's only so many places you could go next, there's only so many places you could go after that, only so many places to go after that, and so on, until eventually you get to the destination, B. If it was this tiny network, for example, you could just examine each of those possibilities and remember the best one, and that would absolutely be a correct algorithm for the problem.
▶︎ 6:22 But also like the shortest paths problem, the number of different possibilities is blowing up very, very quickly, exponentially, as you have more and more places that you need to visit. Again, if you have a network with, say, a couple hundred different spots that you need to visit, exhaustive search would take a unimaginable amount of time. It would not complete in our or anybody else's lifetimes. The hope would be that the TSP also shares with the shortest path problem the existence of an algorithmic shortcut that can be taken advantage of by some algorithm akin to Dijkstra's algorithm. And even though the problems look very similar, and even though there really is this algorithmic shortcut for finding shortest paths, to this day, speaking in 2026, nobody has found a good algorithmic shortcut for solving the traveling salesperson problem efficiently.
▶︎ 7:18 And it's not for lack of trying. Many brilliant minds have thought very hard trying to come up with fast algorithms for solving the traveling salesperson problem. They have made some progress, so it is actually known how to do a bit better than exhaustive search. There are ways of, just like in our multiplication example, of taking redundant work, exposing it, and then reusing computations as opposed to recomputing them from scratch. You can get some amounts of optimization from that idea, but even at the end of the day, after all of those ideas have been exhausted, you're still left with algorithms that just would be unable to solve more than very small instances in a reasonable amount of time.
▶︎ 8:03 Lots of smart people thinking for a long, long time, none of them were able to come up with a fast algorithm for TSP, and so you gotta start wondering. Even though it's superficially similar to shortest paths, maybe the traveling salesperson problem is just a problem of a fundamentally different nature. Maybe it really eludes computation.
▶︎ 8:24 Now, just as a sanity check, and let's not go overboard. If your thought is like, "Oh, let's remember Turing. Let's remember there were these problems like the halting problem, which you can't solve via computer at all." TSP is definitely not one of those undecidable problems. It's definitely not as hard as the halting problem. The halting problem, remember, you cannot solve by computer at all. There is no algorithm that runs in any amount of time which is guaranteed to solve the halting problem.
▶︎ 8:55 TSP, it's a gentler beast. There's certainly a finite algorithm for solving it, because if nothing else, you could enumerate all of the possibilities, and there's only a finite number of possibilities, you could enumerate them all and remember the best. So the traveling salesperson problem, or TSP, if it's a hard problem, it's of a scaled-down nature compared to the halting problems, the undecidable problems that Turing identified and that we discussed in the first episode.
▶︎ 9:24 So if you think about it, all of this puts us in an uneasy state of ignorance. For a problem like the TSP, the traveling salesperson problem, on the one hand, we don't know how to solve it efficiently. We don't know a fast algorithm the way we do via Dijkstra's algorithm for the shortest path problem. At the same time, we don't know how to argue that there is no fast algorithm solving the TSP, the way we do know how to argue that there's no algorithm in any amount of time solving the halting problem. So we neither have an analog of Dijkstra's algorithm nor do we have an analog of Turing's undecidability argument. And so that leaves us not knowing whether or not the TSP is efficiently solvable or not.
▶︎ 10:12 Now, in the era, 1950s, 1960s, where lots of brilliant algorithms researchers were thinking about it, and this may be a little bit egocentric of them, but after trying long and hard, there's a temptation to conjecture, "Well, if I couldn't find an algorithm, probably there is no algorithm." And so for example, Jack Edmonds, who was a legend in algorithm design, we'll talk more about him later, he thought a lot about the TSP in the 1960s. And in 1967, he actually writes in one of his papers, he writes, "I conjecture that there is no good algorithm for the traveling salesperson problem." And we'll talk more about what he means by good algorithm in a second. "I conjecture there's no good algorithm for the TSP."
▶︎ 10:58 And then he says something funny, he says, "My reasons are the same for any mathematical conjecture. First of all, it's a legitimate mathematical possibility, and second of all, I do not know." And if you think about it, if those are the two criteria, he might as well also conjecture that the TSP does have a good algorithm, but in any case, that was Edmonds's conjecture back in 1967. And as we'll see, Edmonds's conjecture, the unsolvability by efficient algorithms of the TSP is actually equivalent to this famous P not equal to NP conjecture. That was one of the first equivalent statements of it. Not the first, but one of the earliest.
▶︎ 11:40 So the plan is, in the next episode, in episode four, that's when we'll do a really deep dive on the P versus NP question. We'll talk about the historical backdrop, so how did researchers come to identifying that as really the key open problem in the field, and then we'll move on and talk about the ramifications of what it would mean if P was equal to NP or P was not equal to NP. But in this episode, my goal is to introduce the two main protagonists in this question. So on the one hand, how to formalize the idea of problems that are efficiently solvable, for which there is a fast, automated procedure for carrying them out.
▶︎ 12:22 And then also these problems like the TSP which, as far as we can tell, it would seem, are fundamentally unsolvable by efficient algorithms. And those are going to be known as the NP-complete problems. So those are the two key goals of this episode, of Episode 3. What is a polynomial-time solvable problem? That's going to correspond to the P in the P versus NP. And what are the NP-complete, or seemingly difficult problems? And that's part of the story on the NP side of the P versus NP question.
▶︎ 12:54 Let's get into it, and let's start with P. What does P stand for? Hold that thought. We will learn that later in the episode, but hold that thought for now. The idea is that P should capture problems that are, in some sense, easy. What does easy mean? It means they should be solvable by a fast algorithm.
▶︎ 13:11 You can think of this as a refinement of Turing's notion of decidability back in his 1936 paper. Turing was interested in problems that can be solved, at least in principle, by computer. Now, we're zooming in on problems that can be solved, in fact, quickly by computer. If an easy problem is one that is solved by a fast algorithm, the question now is, what do we mean by a fast algorithm?
▶︎ 13:38 Intuitively, we want to say something like, "Well, if the algorithm works on problem instances that are interesting to us, like reasonably big, in an hour on our laptop or less, well then, that should be fast. And then if it would take a year to finish on our laptop, then I guess that should not be fast." For example, we've already seen some algorithms that intuitively we would be tempted to classify as fast algorithms.
▶︎ 14:04 If we go back to multiplying two numbers, forget about Karatsuba. Even just the way we were taught to multiply two numbers in grade school, that feels like a pretty fast algorithm. For example, if you had numbers that had thousands of digits, obviously that would be super annoying to do by hand. But the calculations you would do, those thousand partial products, all that stuff, totally trivial for modern-day computers. Tens of thousands of digits, no big deal. So very large numbers you could multiply quickly using even just the method that we were taught in grade school. With Karatsuba's method, obviously it would be even faster.
▶︎ 14:44 Same thing with Dijkstra's algorithm. We didn't talk about it super formally, but remember what you do is you explore in parallel all paths radiating out from the origin until eventually you get to the destination. The idea is that it seems like the amount of work that you do as you do the exploring, you should be able to handle pretty large networks. And again, thousands of intersections and roads, no problem. Tens of thousands of intersections and roads with Dijkstra's algorithm? No problem. Even on a modern laptop, that would complete very, very quickly.
▶︎ 15:17 Intuitively, those are fast algorithms. You can handle problem sizes that would be, at best, annoying, at worst, impossible to do by hand. And you can do them in less than a second on your laptop. So that's pretty cool. That's pretty useful.
▶︎ 15:31 Meanwhile, exhaustive search, for example, for shortest paths, examining all the different options, intuitively that feels like it should not be a fast algorithm. Even for pretty small networks, really enumerating all of the possible routes might take a year, even for very small networks. And again, for medium-sized networks, forget about it. You're talking about it would take billions of years to complete. Obviously, that would not be a fast algorithm. So that, intuitively, is the difference between a fast algorithm and a slow algorithm.
▶︎ 16:04 But that's sort of intuition. You should be saying, "I thought the P versus NP question was a math problem. So there must be an actual math definition then of what is an easy problem, or a math definition of what is a fast algorithm." You're right. You're right, you're right. There is, there is. I'll give that to you next. You may be sorry you asked, but I'll give you the actual mathematical definition.
▶︎ 16:31 We're going to identify fast algorithms with what's known as a polynomial-time algorithm, and I'll tell you how to think about that in concrete terms. But just for now, the terminology is polynomial-time algorithm, and the P, that stands for polynomial. What's a polynomial? Polynomials are things like X plus 3X plus 2, or X to the tenth minus 9 times X to the seventh plus 3. These are the, if you've ever seen, if you haven't seen these before, don't worry about it. If this rings a bell, these are examples of polynomials. So they're simple functions of one input. You plug in a number, and it's a simple formula by which you compute an output number. Those are examples of polynomials.
▶︎ 17:21 And so this is also exactly in Edmonds' conjecture, you might recall, he said, "I conjecture there's no good algorithm for the TSP." Edmonds also had in mind polynomial-time algorithms, the same definition. Around the same time, Alan Cobham, this was in a 1965 paper, he independently advocated for identifying efficient computation with polynomial, polynomial number of operations. So this was an emerging idea in the mid-1960s. Sometimes you hear this identification of feasibility with polynomial number of operations. Sometimes you hear that called the Cobham-Edmonds thesis, after those two researchers, and in homage to the Church-Turing thesis.
▶︎ 18:03 To understand this concept of a polynomial-time algorithm, it's crucial to think about the running time of an algorithm, meaning how long it takes to complete its task, the running time of an algorithm as you make the problems that it's solving bigger and bigger and bigger. For example, think about multiplying two numbers. Presumably, the more digits there are in those numbers, the bigger the numbers are, the longer it's going to take to figure out what their product is. You can see that intuitively if you just think about filling up the board with the original grade school algorithm. But the question is going to be, it gets slower as the numbers get bigger, but how much slower? If the numbers are twice as long, does the algorithm take twice as long to multiply them? Does it take four times as long? Does it take a thousand times as long?
▶︎ 18:53 Same thing with shortest paths, or say Dijkstra's algorithm. Presumably, the algorithm's going to take more and more time as the network that it has to navigate through gets bigger and bigger. But again, how much more? If I double the network size, does it take twice as long or four times as long, or what? That's the mindset you want to have in understanding what this polynomial-time algorithm definition means.
▶︎ 19:16 A very concrete way of thinking about it is in terms of something you might have heard of, Moore's Law. Moore's Law was first stated by Gordon Moore, who at the time was at Intel. This was in the mid-'60s. And Moore's Law asserted that the speed of computers doubles every two years. Sometimes you hear versions of this where it's 18 months or 12 months, whatever. And really it's about the number of transistors, not the speed, but again, whatever. That basically computers keep getting faster, let's call it twice as fast every two years.
▶︎ 19:49 Now, you would hope that when your computer gets significantly faster, you can solve significantly bigger computational problems than you used to be able to, in the same amount of time. Like say in an hour. Say you want to multiply two numbers, you want to find the shortest path in a network, you're willing to give the computer an hour to do it. If you buy the next generation of computers, it's twice as fast, hopefully you can multiply bigger numbers, hopefully you can find shortest paths in bigger networks than you could before. But how much bigger?
▶︎ 20:21 What would be great is if your computer gets twice as fast and you can solve twice as big of problems. You can multiply numbers that are twice as big, you can search through networks that are twice as big. And that would be the case if you are talking about what's known as a linear time algorithm. That would correspond to a polynomial, just like 10X or something like that, without any of these X squareds or X cubes or anything like that.
▶︎ 20:44 Other algorithms give you, do better with more computational speed, but not quite as rapidly. So for example, if you had what's called a quadratic time algorithm, that would be like grade school multiplication. If you remember, when you do grade school multiplication, if you have numbers that have like 10 digits, you're going to fill up 10 rows, your 10 partial products, and they'll be ballpark something like 10 columns. So you're going to be filling in like 100 numbers if your numbers have 10 digits each. So notice that the amount of work you need to do, the size of the table you need to fill in is blowing up as the square of the number of digits in each number. Multiply two 10 digit numbers, you're going to have to fill in 100 numbers. Multiply two 20 digit numbers, you're going to have to fill in 20 times 20, or 400 numbers.
▶︎ 21:32 So for a quadratic algorithm, if you wait for Moore's Law to give you computers that are twice as fast, you're not going to be able to multiply numbers that are 100% bigger, that are twice as big as before, but you will get a percentage increase. You'll be able to multiply numbers that are 41% bigger than you used to be able to. In, again, a fixed amount of time, a minute, an hour, whatever your time budget. If the algorithm did a cubic number of operations rather than quadratic, again you would get a percentage increase from a doubling of the computing power. Not as big a percentage increase, now it would be 26% instead of 41%, but still you would get a percentage increase in the problem size you can solve in a given amount of time.
▶︎ 22:16 So that is what we mean by a polynomial time algorithm. If someone just gives you a faster computer, you will be able to solve bigger problems with that algorithm, and the increase in the problem size you can handle will be a percentage increase, for each doubling of the computing power. That is what a polynomial time algorithm means.
▶︎ 22:36 So what would be a not polynomial time algorithm? Well again, think about exhaustive search. Think about having to examine an exponentially large, an astronomically large number of different options. Even just think about our simple shortest paths, where if you have four of these in a row, you have to look at 16 options. If you have 10 of these in a row, you have to look at 1,024 options. If you have 20 in a row, it's roughly a million and so on. Every time you add another one of these gadgets, another binary decision to make, that doubles the number of options that you have to search through exhaustively.
▶︎ 23:16 So if I give you a computer that's twice as fast and you're doing exhaustive search, what it allows you to do is add one more of these binary decisions to the network. That is the only increase in power you get from a doubling of the computing power. Your computer is twice as fast, and now instead of handling a hundred binary decisions, you can handle 101. It's a very demoralizing increase in problem size that you can handle if you're using an algorithm which is not a polynomial time algorithm. You double the speed of the computers, and the problems you can solve are barely bigger than before. So that's formally what we mean by a fast algorithm. Polynomial time algorithm, a doubling of computing power gives you a percentage increase in the problem size you can handle.
▶︎ 24:06 And then P just refers to, is a definition of easy problems as those that can be solved by polynomial time algorithms. And again, we know some examples. Multiplication, that can be solved by a polynomial time algorithm. Already the grade school algorithm would qualify. Again, shortest paths, that's a polynomial time solvable problem because you can solve it using Dijkstra's algorithm, and Dijkstra's algorithm runs in polynomial time. And this is exactly the sort of algorithm which even now, in 2026, nobody has found for the TSP, for the traveling salesperson problem, and yet at the same time, no one's been able to establish that such an algorithm for the TSP does not exist.
▶︎ 24:45 That's a nice milestone in this episode. Really, this episode has two goals. One, to understand easy problems. We just determined that. That's these problems in P, problems that have fast algorithms, where fast algorithm means a polynomial time algorithm. And then the other protagonists that we have to study is so-called NP-complete problems.
▶︎ 25:04 But before we get to that, which we'll do in a second, I want to just briefly relate our discussion so far back to everything we talked about in episode one, back when we were talking about Turing and the basic notions of undecidability and decidability. What can be solved in principle by computers, and what is unsolvable, even in principle, by computers. So what we just saw, this idea of easy problems, polynomial-time solvable problems, that can be viewed as a sort of refinement, a strengthening of Turing's notion of decidability. For Turing, solved by computer meant just solved by some algorithm which is guaranteed to eventually halt. And here, we want to say, "No, no, no, no, we'd actually like the algorithm to run quickly, like complete in our lifetimes, or even in, ideally, under a second." So polynomial-time solvability can be thought of as a strengthening of Turing's decidability.
▶︎ 25:57 So the other part of the equation that we're missing is, what would be the analog of undecidability? Problems that are unsolvable by computer. So Turing had the halting problem. Here, we have a candidate. We've got the traveling salesperson problem, the TSP. We know it's not undecidable, because if nothing else, you could solve it by just enumerating all of the options. But the conjecture is that it's unsolvable efficiently. So we need some notion of, what does it mean for a problem to be this scaled down version of undecidable? Yes, solvable in principle, but no, not solvable reliably in practice.
▶︎ 26:36 So that is the concept of NP-completeness. That is going to play the analog of Turing's undecidability notion. If you think about it, we're also refining the Church-Turing thesis that we discussed back in episode one. So just to remind you, in episode one, we had this quaint model of a Turing machine, and at some point we asked, "Are you serious? Are you serious that this kind of parable about a human computer on a roll of tape is supposed to actually capture whatever we could possibly do with any technology for computation, ever?" And the answer is, yeah. Yeah, actually, it does. And that's the Church-Turing thesis. The belief that, in fact, Turing machines can express any computation you could express in any other way.
▶︎ 27:19 And as we talked back then, the way you amass support for that thesis, for that belief, is literally just you enumerate every other way you can think of to express computations, and you show one-by-one, whatever it is, you can equally well express those exact same computations using a Turing machine. Remember, that's what Turing did in the appendix of his paper, where he showed that Church's lambda calculus expresses the exact same computations as Turing machines. And we now know that's true for lots of other systems as well. So that's review from episode one.
▶︎ 27:52 But let's just think about what we just did now. In episode one, we identified computation with what Turing machines could do. Now, we're identifying efficient computation with what specifically polynomial time Turing machines can do. Meaning Turing machines that are guaranteed to complete their task in a polynomial amount of time. These are Turing machines whose, if you give them twice as many steps, they can handle problem sizes that are a percentage increase larger.
▶︎ 28:26 So this is now a bolder thesis. We're saying not just in general, through arbitrary computations, do Turing machines capture them. We're saying that exact same formalism that Turing introduced, that exact same notion of Turing machines, is also the exact right formalism to capture everything there could be to know about efficient computations. And so that is something known as the extended Church-Turing thesis, and to be clear, that was stated neither by Church nor by Turing. That came later when the focus zoomed in on efficient computations. So that's something we'll talk about a fair amount in episode five.
▶︎ 29:05 And in particular, there have been meaningful challenges to the extended Church-Turing hypothesis, unlike the original Church-Turing hypothesis. So that'll be a very fun discussion involving, for example, quantum computers. Little bit of a forward pointer to episode five.
▶︎ 29:21 So now that we've covered the first protagonist, P, easy problems, and now that we've had this digression to situate what we're talking about in terms of Turing's original theory, let's move on to the other main goal of this episode, which is to understand what does that NP in P versus NP mean, and specifically, what is the theory of NP-completeness? So honestly, NP-completeness might well be certainly one of, if not the top, intellectual export ever from computer science to other disciplines. If you go to a citation database, and you look, not in computer science, not in engineering, but just even restrict your search to the natural sciences and the social sciences, you will encounter thousands and thousands of papers that discuss the concept of NP-completeness. It is very, very rare for a concept this technical to cross that many disciplinary boundaries and have that much impact in so many different fields. It's a really big deal, the impact NP-completeness has had in the half century plus since it was developed.
▶︎ 30:27 Now, one question probably on your mind is, "What's up with this alphabet soup," NP, NP-complete? Okay, so there's a story there, and I'll tell you the full story behind the terminology next episode. Right now I want to plow ahead and talk about why did people invent this theory in the first place? What is its purpose?
▶︎ 30:48 So remember, you're in the 1960s. You've got lots of brilliant people cracking all kinds of different algorithms. But some problems remain stubbornly unsolved, like the traveling salesperson problem, like the TSP. Leading, for example, Jack Edmonds to conjecture in 1967, "I'll bet you just cannot solve the TSP with a polynomial time algorithm."
▶︎ 31:11 At the same time, honestly, subsequent to Turing's paper, proofs of limitations on what algorithms can do were few and far between. Now we have a better appreciation that algorithms can do wild, crazy things, like Karatsuba's multiplication method. How would you ever think of that? Who knows what other kind of amazing, unexpected, clever things different algorithms can do. So it's very, very difficult to prove that algorithms can't do things, Turing's theory of undecidability put aside. Very difficult to show that algorithms cannot do things.
▶︎ 31:44 And so that's then a quandary. So if you're in computer science, either you care about algorithms or you care about the limitations of algorithms. You've got something like the TSP, no one has any ideas how to solve it, and no one has any ideas how to prove you can't solve it. What do you do? Are you all supposed to just go home? Should just everybody work on that problem and nothing else until it gets resolved? Well, that's not very pragmatic, from a scientific perspective.
▶︎ 32:10 You might have a conjecture, and even in the '60s, and it's still true today, most people would conjecture that, in fact, there is no good algorithm, no fast algorithm for the TSP. You have to be ready for the possibility it's going to take a very, very long time to have a fully foolproof, mathematical proof of that fact. So how do you make progress? How do you make progress? And this is where the theory of NP-completeness comes in. In the absence of a convincing mathematical proof that the TSP problem cannot be solved by any fast algorithm, you have mathematical evidence making it ever more unlikely, ever more implausible that there could be a fast algorithm for the TSP.
▶︎ 32:54 And this is the brilliant idea in NP-completeness. You give up, at least temporarily, on proving difficulty in an absolute sense, proving that the TSP is hard, full stop. Temporarily pause that ambition and you say, "Well, let's just resort to relative difficulty." Let's at least be able to say that the TSP is at least as hard as many, many, many other computational problems. And that is the high level idea of NP-completeness.
▶︎ 33:24 But what does that actually mean, prove that TSP is as hard as lots of other stuff? One question is, what do I mean by "as hard as?" We'll get to that. The other thing would be, what's all this other stuff? What is the most compelling evidence you could provide of the difficulty of solving the TSP? You could say, "Well, what if the TSP was literally as difficult as every other computational problem in existence?" That would sound pretty convincing. That'd be like, whoa, that's got to be a hard problem. It's as hard as every other problem anyone's ever thought of.
▶︎ 34:00 The issue is, that statement we know is not true. We know there are problems completely unsolvable, even in principle, by computers, like the halting problem. And the TSP is solvable in principle by computer because you could use exhaustive search. Because there is a bounded number of easily checked solutions, you could enumerate them all and remember the best. TSP definitely not as hard as the halting problem, but we still think it's harder than, say, computing shortest paths.
▶︎ 34:31 So what would that look like? Could it be that TSP... What would be the next most ambitious thing to say, that's not obviously false? That's what we want to think about. Maybe TSP is as hard as anything else that resembles it. What does that mean? Maybe it's as hard as any other problem that, like the TSP, can be solved in principle through exhaustive search of easily checked solutions. So maybe the TSP is as hard as every problem that can be likewise solved by exhaustive search through a number of easily checked solutions. That, in fact, is going to be the definition of an NP-complete problem. As hard as lots of stuff, what is the lots of stuff? Anything else where you know a solution when you see it.
▶︎ 35:28 For example, think about Sudoku. If you're talking about very hard Sudoku puzzles, it might take a while to figure out the solution. They drive me crazy, to be honest, these hard Sudoku puzzles. So many other things I could be doing with my time. And somehow, anyways. But if someone else solved it and showed it to me, it would be very easy for me to inspect it and say either, "Awesome job, you solved the Sudoku puzzle," or, "Sorry, there's like two twos in this row," or that there's some other violation of the rules of Sudoku. So handed a solution on a silver platter, very simple to check whether or not it really is a solution. Same thing with TSP. If someone showed you a way of visiting all of the intersections that took at most an hour, it would be straightforward to verify that their solution had that problem. It'd be straightforward to verify that it went to every single intersection and that the total travel time was an hour or less.
▶︎ 36:29 So that's going to be what we mean by an NP problem, a problem we're handed a solution on a silver platter, it is straightforward to check whether or not it's correct. So what does NP-completeness going to be? It is going to be a problem that is as difficult as any other problem that likewise has easy to recognize solutions, and for that reason, can be solved in principle by exhaustive search.
▶︎ 36:58 So circling back to Edmonds' conjecture. Remember Edmonds' conjecture that there's no good, meaning polynomial time algorithm for the TSP. At the same time, no one knows how to prove that. And so this discussion has all been how do we amass evidence, absent a formal proof, how do we amass evidence that in fact there might not be an efficient algorithm for the TSP? The idea is relative difficulty. Prove that the TSP is at least as hard as tons of other problems.
▶︎ 37:24 We identified, well, it seems like the maximally ambitious thing we could do is prove that the TSP is as hard as any other problem that resembles it in the sense of being solvable by exhaustive search through a bunch of easily checked solutions. That's going to be the notion of NP-complete. And indeed it is known now that the traveling salesperson problem is one of these NP-complete problems. Actually, it turns out Sudoku, properly formalized, is another example of an NP-complete problem. And there are thousands and thousands of others. Not just in engineering, but again also in the natural and social sciences.
▶︎ 37:59 And honestly, if you stop and think about it for a while, just the fact that any problem could be NP-complete, it's pretty wild actually. It kinda ties back, I don't know if you remember, episode one, we were talking about universality. We were talking about the ideas going into Turing's arguments around undecidability. And back then, we had this notion of a universal machine, universal Turing machine, like your operating system that sort of can take as input code of a program and simulate that program. So that was our first appearance of universality.
▶︎ 38:30 Here, we're seeing it very differently. We're seeing not computing devices that are universal, but problems that are universal. That's what NP-complete problems are. It is a single problem like the traveling salesman problem which simultaneously encodes thousands of other problems. Every other problem with easily checked solutions, every single problem of that form is a thinly disguised version of the traveling salesman problem, including Sudoku. They're really just two thinly disguised versions of the exact same problem. And that is true for all NP-complete problems.
▶︎ 39:09 Kind of amazing when you think about it. So universal problems of this type, we don't have a proof of this, but boy, sure seems like they should be hard problems. It sure seems like it would be pretty remarkable if you had a fast algorithm for one of them. Because again notice, by virtue of being universal, by virtue of encoding all other problems that have easy to recognize solutions, one fast algorithm for one NP-complete problem, for example, the traveling salesperson problem, that algorithm alone would already solve thousands of these problems, all problems out there that have easily verified solutions. That is the power of universality. And it certainly is suggestive that there may not be a fast algorithm for the TSP, because if there were, the ramifications would be world changing, would be really remarkable.
▶︎ 40:04 Another thing that's, if you think about this a little harder, remarkable. So what this means is that all NP-complete problems share the same computational fate. Either all of them can be solved by fast algorithms or none of them, because you solve any of them with a fast algorithm, it's NP-complete. So if you solve any of them, you immediately solve them all. So it's all or nothing for NP-complete problems, which means there's only two possible worlds. We don't know which world we're in, but at least there's only two possible worlds we could be living in.
▶︎ 40:44 Let me show you a cartoon of those two worlds. So let's start with the world as Edmonds envisioned it. World number one. In world number one, we're gonna think about all of the problems that have solutions that can be recognized quickly. These are the so-called NP problems. So shortest paths would be in here, multiplication would be in here, TSP would be in here, Sudoku would all lie in here. So TSP would be an example here, and maybe shortest paths would be an example here.
▶︎ 41:43 And the way Edmonds envisioned the world, there is a difference between say computing shortest paths or solving the traveling salesperson problem, that this should be the regime where you are not efficiently solvable, and this is the regime where you are efficiently solvable. So this would correspond to P. The problems that don't merely have easy to check solutions, but in fact it's easy to find a solution, to compute one from scratch. Solvable by fast, meaning polynomial time algorithms. And then NP, remember, means easy to check solutions. It doesn't mean easy to find. Again, think Sudoku. It's not so easy to find the solution, but it's easy to check the correctness if someone else hands you an alleged solution on a silver platter.
▶︎ 42:49 And so in world number one, in fact, we're gonna have all of the NP-complete problems. And so remember, the NP-complete problems are the hardest ones in NP. And I'll make that precise using reductions shortly. But NP-completeness, the NP-complete problems are the hardest ones. If you can solve them, you can solve all the problems in NP. Anything that has easy-to-check solutions. You might be wondering what's up with this kind of no man's land. We'll talk about that eventually. I'll leave that as a mystery for the moment.
▶︎ 43:22 But in Edmonds' view, shortest paths should be efficiently solvable. TSP should not be efficiently solvable. And the theory of NP-completeness clarifies that Edmonds' conjecture is not really about just the one problem of the TSP. Edmonds' conjecture is actually simultaneously about all NP-complete problems at the same time. All NP-complete problems share the same fates. You solve one, you solve them all. If you solve one, and therefore you solve them all, all of this collapses.
▶︎ 43:54 So that gives us World Number II, which is not what Edmonds was conjecturing. And so this corresponds to the world where P equals NP. And this would say that for every single problem for which you can easily recognize solutions, generically, there's an algorithmic shortcut, akin to what we saw in shortest paths. Even though there's an astronomical number of possibilities, by virtue only of being able to recognize a solution quickly, it's automatically true that you can sift through all of the options and find one quickly. That's what it would mean to solve an NP-complete problem and have all of this collapse. So this would be solvable by fast algorithms. Whereas by contrast, in World Number I, the NP-complete problems would, as Edmonds conjectured, be unsolvable by fast algorithms.
▶︎ 45:06 So what the theory of NP-completeness does is it reduces what would seem to be thousands of different open questions. For each of these different problems you might wanna solve, is there a fast algorithm or is there not a fast algorithm? So the theory of NP-completeness doesn't give us the answer. We still don't know. But it takes what seem to be thousands of disparate open problems and compiles them down into just one. Is there a fast algorithm for any NP-complete problem, TSP, Sudoku, or otherwise? A fast algorithm from one gives you a fast algorithm for all, and determines which of these two worlds is the one we're living in. The P versus NP question is exactly understanding whether we live in World Number I, that would be P not equal to NP, or whether we live in World Number II. That would be P equal to NP.
▶︎ 45:59 So I mentioned earlier, John von Neumann's slightly cynical quote about how you don't really understand mathematics, you just get used to it. And I mentioned at that time that one of the things you get used to when you work with computation and algorithms is how tiny changes to a problem's description seem to radically change how hard it is to solve. So in terms of these pictures, that means you can take two different problems that resemble each other quite closely, and yet one is down here, where you know there's a fast algorithm for it, and the other, like TSP, might be NP-complete, where we tend to believe that there is no fast algorithm for it.
▶︎ 46:32 But then there's also a second, a dual, equally strange consequence, which is that you can take problems that look nothing like each other, nothing at all. Like TSP and Sudoku. What do they have to do with each other? They both have easy-to-recognize solutions, but come on, that seems like a pretty weak link between the two problems. So they look totally different, and yet they're exactly the same. They're both NP-complete problems. All NP-complete problems are, in some sense, thinly disguised versions of the exact same problem. So tiny changes sometimes make a huge difference. Huge changes sometimes make no difference when it comes to the computational difficulty of solving a problem.
▶︎ 47:10 There's one more thing that I really feel like I owe you in this episode, which is explaining what it means for one problem to be as hard as another. Because remember, how are we defining NP-complete, informally thus far? As hard as any NP problem. Where an NP problem is just one that has easy-to-recognize solutions. And again, just because it's easy to recognize one doesn't mean it's easy to find one. Think again about a hard Sudoku puzzle. I.e., has easy-to-check solutions.
▶︎ 48:06 This is what I told you NP-complete means. It's as hard as any other problem where you sort of know a solution when you see it. But your question should be, what does this mean exactly? As hard as. If TSP is supposed to be an NP-complete problem, well, Sudoku is an example of an NP problem. And so I guess it better be true that the TSP is as hard as Sudoku. So what does that mean? What does it mean that TSP is as hard as Sudoku?
▶︎ 48:44 The answer is going to be a reappearance of something we talked about back in episode number 1. In episode number 1, we talked about the key ideas in Turing's argument that the halting problem is undecidable. And there are three steps. The first step was about the universal Turing machine and simulation. The second step was adapting Cantor's diagonalization technique, also used by Gödel, to show the existence of some kind of peculiar undecidable problem. And Turing wasn't happy with that. Turing wanted to show that undecidability was a really practically relevant concept, that there were computational problems we might really care about that are also undecidable, so he chose the halting problem. And what he did is he used a reduction from the peculiar undecidable problem to the halting problem, and the reduction spread the undecidability from the peculiar problem to the halting problem.
▶︎ 49:44 So we're going to do the exact same thing here. We'll use reductions. This time, it's important the reductions will be efficient, otherwise it's the same, and we will use reductions to spread NP-completeness from one problem to another, intractability from one problem to another. We also talked back in episode number 1, we're all familiar with the reductions from real life. I gave you two examples. One was getting home from drinks, happy hour after work. If you sort of know how to get home from work, then getting home from happy hour reduces to that problem just by walking back to where you work. Or if you're an Excel spreadsheet wizard but you don't know how to use Google Sheets, well there's a reduction from the latter to the former just by exporting the data into Excel.
▶︎ 50:25 So the point is, you can solve one problem very easily if you know how to solve another. The first problem reduces to the second problem. In other words, all you need to do is know how to solve the second problem, then you're also going to know how to solve the first problem. So that's what we mean by a reduction.
▶︎ 50:51 Imagine we had a reduction from Sudoku to the traveling salesman problem. You want to come up with a solution to a Sudoku puzzle, and I'm going to show you it's enough to just figure out how to compute a short path visiting all of the intersections in a suitable network. Now, you might say, "Well, how would you argue that? Those seem like totally different problems." And reductions is a bit of an art in its own right. It's something that you would sort of train in if you studied computer science. And just take my word for it that it's not that bad.
▶︎ 51:21 There's a lot of annoying details that I would never cover in a series like this, but you can in fact show that you give me a Sudoku puzzle that you want a solution, I'll give you back a network where any short traveling salesperson tour in that network will give you back a solution to the Sudoku puzzle that you started with. In other words, to solve Sudoku, all you need to do is solve TSP. To solve Sudoku, all you need to do is know how to solve TSP. That is a reduction from Sudoku to TSP, and that is what we mean when we say TSP is as hard as Sudoku.
▶︎ 52:09 Now to qualify as NP-complete, it can't just be that one particular problem with efficiently verifiable solutions reduces to you. It has to be that every problem with efficiently verifiable solutions reduces to you. So not just Sudoku, but literally anything else you could think of. Any other problem with efficiently verifiable solutions, if you put it here, that problem should reduce to the TSP. That's what it means for the traveling salesperson problem to be NP-complete.
▶︎ 52:42 Now, the good news is that if you could prove a problem like the TSP NP-complete in this sense, where literally all you need to do is solve the TSP and you unlock fast algorithms for thousands of other problems, the good news is, that's actually starting to be pretty convincing evidence that maybe there is no fast algorithm for the TSP. Again, because the ramifications of that algorithm would be so remarkable. The bad news is, you should be like, "Okay, but why would any problem be NP-complete? That sounds crazy. Why would there just be a single problem that by itself unlocks thousands?" And again, a priori, without this brilliant work from the '60s and '70s, I don't know why you would think that such NP-complete problems could possibly exist.
▶︎ 53:26 But then again, before Turing's work in 1936, it's not obvious that there would have been computational tasks that are undecidable, that are fundamentally unsolvable by computer. So what we really need is an analog of Turing's results around undecidability and the existence of undecidable problems, like the halting problem, we need an analog, but now not for undecidable problems. We're working with all these problems where you could solve them, if nothing else, by exhaustive search, but a scaled-down version of Turing's undecidable problems. We need NP-complete problems, and ideally NP-complete problems that people really care about.
▶︎ 54:04 The analog of Turing's big result from the 1936 paper is work done in the early 1970s, kind of in parallel on both sides of what was then the Iron Curtain, so happening in parallel in North America and in the Soviet Union, and something known as the Cook-Levin theorem. The Cook-Levin theorem, which is really one of the most important mathematical results in computer science, establishes that in fact there are natural problems, problems we'd really like fast algorithms for. There are natural problems that are in fact NP-complete. So problems that on the one hand have easy to check solutions, but on the other hand, simultaneously encode every other problem that likewise has easy to check solutions, NP problems that are universal in this sense.
▶︎ 55:24 This is what we're talking about. I'm not really going to talk about the proof. The proof gets a little messy. Stephen Cook proved it in North America around 1971. Leonid Levin proved it on the other side of the Iron Curtain in the Soviet Union around that same time, around 1971. Levin's work went unknown. This is how life was in the '70s. For those of you that were around then, you'll remember, Levin's work went unknown in the West for a long time. I forget if it was the late '80s or early '90s, but for a long time, it was not known in North America and Europe that Levin had done this sort of parallel work around NP-completeness in the Soviet Union. But these days, they both get equal recognition and we call it the Cook-Levin theorem.
▶︎ 56:04 There exist natural NP-complete problems. Neither Cook nor Levin actually considered the traveling salesperson problem. That was done by a third researcher, Richard Karp. We'll talk more about his story in the next episode.
▶︎ 56:18 NP-completeness, amazing concept. Hard to believe that these problems even exist. The breakthrough Cook-Levin theorem is what gives us that initial foothold. It shows us that indeed some problems are NP-complete, really a scaled down version of Turing's result that there exists natural undecidable problems. And once you have one, that's the thin end of the wedge. As soon as Turing exhibited the one natural undecidable problem, many others came to follow. Exactly the same story has happened for NP-completeness. Once you have the thin end of the wedge, a couple NP-complete problems to work with, it then becomes much easier to show that many, many other problems are likewise NP-complete.
▶︎ 57:01 That's a lot of technical content for one episode. Let me just leave you with a little history, a little bit of a parable. One question, I don't know if you ever thought about, but it's interesting to ask, what makes a researcher great? What are the key qualities to really being successful doing innovative research? Talent? Yeah, sure. Obviously. Mentoring, really good mentoring? Super helpful. Luck? Definitely doesn't hurt. But probably one of the most important and underrated traits in doing great research is just tenacity and relentlessness in the face of obstacles.
▶︎ 57:42 And in mathematical research, the obstacles will come fast and furious. The mathematical obstacles will come fast and furious, and for many of us in life, the obstacles also come fast and furious. And the best researchers just do not give up. They're relentless. That's been my experience.
▶︎ 57:55 So let me give you, we were just talking about Cook and Levin, who did this absolute genius work in the early '70s inventing the theory of NP-completeness. Stephen Cook was an assistant professor in the math department at Berkeley in the late '60s. They denied him tenure in 1970. He'd already done a bunch of good work by that time. He exacted revenge by moving to the University of Toronto, where he's still Professor Emeritus to this day. And the next year, inventing the theory of NP-completeness, which led to him getting, for example, the Turing Award in 1982. The Turing Award, if you haven't heard of it, is the sort of Nobel Prize of computer science.
▶︎ 58:32 And obviously, Berkeley regretted that. I mentioned Richard Karp just a second ago. He was in the computer science department, whereas Stephen Cook was in math. So he wasn't part of that decision, but in hindsight he said, Karp says, "It's to our everlasting shame that we," meaning he and his colleagues in the computer science department, "were unable to persuade the math department to give him tenure."
▶︎ 58:53 The math department, it's funny, because I don't know about you, but the first time I learned this stuff, Cook-Levin and whatnot, my brain just started to hurt. It was just hard, deep stuff. It was fascinating, intriguing. I was like, "Oh, I want to know more about this." But my brain hurt. I don't know if you've had that experience. You're not the only one. But to the Berkeley math department, they said, "Yeah, this is a little too applied for us." That was part of the reason for the tenure rejection.
▶︎ 59:18 And for context, this was Berkeley, like I said, did have a computer science department at that time. Many places did not. So this was back in the days where computer science was struggling to be taken seriously as an independent and deep discipline. Berkeley at that time did have a computer science department, but many other top universities did not. You might remember in a previous episode, we talked about the snarky comments by Harvard professors in the 1970s around, "We don't need a department of microscope science or telescope science. So why should we have one of computer science?" So this is ballpark that same era. So that's probably part of the politics going on around Cook's struggles there at Berkeley. But like I said, he exacted some sweet revenge.
▶︎ 1:00:00 Leonid Levin, meanwhile, he was doing this work in the Soviet Union. And for various political reasons, he was really struggling to secure a top level, permanent academic position in the Soviet Union. So he immigrated to the States in '78. Actually did a second PhD very quickly at MIT, and then promptly joined BU, Boston University, where he remains a professor to this day. He, for example, was given the Knuth Prize, which is the lifetime achievement award in theoretical computer science, in 2012. Presumably, he would have shared the Turing Award with Cook, I would imagine, if his work had been known at that time. But again, back in the Cold War, advances in the Soviet Union came pretty slowly to North America and Europe.
▶︎ 1:00:44 But in any case, the point of these stories is, sometimes you see, and it's not just researchers. Let's focus on researchers, very successful people. And sometimes they make it, it can look a little almost effortless or preordained, like of course they're this successful. How else could this story have wound up? But in my experience, getting to know a lot of great researchers very well over the years, they almost always had to push through a number of super tough obstacles. Again, both the mathematical and the non-mathematical kind, to get to where they are today.
▶︎ 1:01:18 So I'll leave you with that, but get excited, because next episode is the deep dive on the P versus NP question. I'll see you there.