▶︎ 0:01 In the last episode, we discussed the most important open problem in all of computer science, the P versus NP question. Let's recap that briefly. Conceptually, this is a very deep question. It asks the following question about the nature of computation. Do easily checked solutions, like you have in, say, the traveling salesman problem, the TSP, or in Sudoku puzzles, does the existence of easily checked solutions automatically imply that there are algorithmic shortcuts that can be taken advantage of by fast algorithms as we have, for example, specifically in the shortest path problem?
▶︎ 0:40 Is every NP problem, problems with you-know-it-when-you-see-it solutions, also solvable by a fast algorithm? And remember, we're identifying fast algorithms with algorithms that run in polynomial time, algorithms that when you give them twice as much computing power, there's a percentage increase in the size of the problems that they're able to solve within a fixed time budget. I showed you on the board that we're in one of two possible worlds. If you believe Edmonds' conjecture back from 1967, if you believe that, in fact, there's no polynomial time algorithm, no good algorithm for the traveling salesman problem, then if you look at the space of all NP problems, remember these are all problems where you can efficiently check solutions if someone hands you one on a silver platter, Edmonds says really there's different regions within this sea of NP problems.
▶︎ 1:34 There's the easy ones, like the shortest path problem, which we can solve using Dijkstra's algorithm, and there's the hard ones like TSP, which Edmonds wasn't able to solve, Dantzig wasn't able to solve, Karp wasn't able to solve. You might conjecture that, in fact, that's just this different hard region within the set of all NP problems. And you can zoom in further here and identify these universal NP problems, like an NP problem to rule them all. That's, remember, what we meant by NP-complete. The NP-complete problems, if you think of the problems going from the easiest to the hardest, the NP-complete problems are all the way up at the top.
▶︎ 2:13 They are at least as hard as anything else in here, where as usual, "as hard as" just means there's a reduction. So everything in here reduces to the NP-complete problems. You solve any NP-complete problem, and you would solve everything in this whole moat of NP problems. This is world number one, and this is the world that Edmonds, among others, conjectured, and this corresponds to the P versus NP question being resolved in them being different.
▶︎ 2:44 Now, by virtue of their universality, by virtue of being one NP problem to rule them all, we also learn that all NP-complete problems share the same computational fate. Either all of them are solvable by fast algorithms or none of them. The other world is one in which all of them are in fact solved by fast algorithms, and that is world number two, P equal to NP. This is the P versus NP question we introduced last time. We know we're in world number one or world number two. That's what the theory of NP-completeness tells us, but we don't know which one.
▶︎ 3:24 There's something I left as a mystery. I think now's as good a time as any to demystify it, which is, what in world number one, the P not equal to NP world, what's this? I said, if we think about problems going from easier to harder, the easiest ones are the ones we have fast algorithms for, the hardest ones are the NP-complete ones, the universal NP problems. What's in the middle?
▶︎ 3:50 These are sometimes colloquially known as NP-intermediate problems. I'm not sure if you can see that red, so let me use the green instead. Colloquially referred to as NP-intermediate, meaning problems which are believed to, on the one hand, not be solvable by any polynomial time algorithm, on the other hand, are believed to not be NP-complete, are not so hard as to capture all problems with efficiently verifiable solutions.
▶︎ 4:29 Now, your first thought would be, well, maybe in a very simple world, maybe what we'd love to see is maybe there's just this totally simple dichotomy. You look at all the problems where you can check solutions easily, either there's a fast algorithm or they're NP-complete. You might wonder if that's what the world is like. And in fact, we've known since the '70s that it's not.
▶︎ 4:49 There's a result known as Ladner's theorem from the 1970s which says if you're in world number one, so if you don't have this total collapse, if you do have a separation between P and NP-complete problems, then in fact there must be problems in between. P not equal to NP implies the existence of these NP-intermediate problems.
▶︎ 5:13 Now, Ladner's theorem is just sort of existential. It just sort of produces this very weird and very peculiar problem which, assuming P not equal to NP, is provably neither easily solved nor NP-complete. But what's cool is at this point we also have some pretty interesting candidates for species that might live in this part of the habitat. So let me give you one example, which would be factoring.
▶︎ 5:48 This is an important problem. This is, again, a problem of number theory. I give you a number, like 100, and your job is to express it as the product of primes. It turns out there's a unique way to do this. For each natural number, there is one and only one way to decompose it as the product of primes. Remember prime is a number whose only divisors are one and itself.
▶︎ 6:13 So like 100 for example, you could decompose as 2 times 2 times 5 times 5. 2 and 5 are both prime numbers, and so this is a way you could build up a hundred using just the primes 2 and 5. Obviously not so hard to factor 100, but imagine this instead a number that has, I don't know, 1,000 digits. Pretty big number. We can write it down, but it would be a long number. What about finding a factorization of that number? Because that's something you could easily do by computer.
▶︎ 6:48 And in case you think I'm just fabricating hypothetical nonsense problems, in cryptography these are exactly the length of the numbers that you work with. You would work with numbers that have, ballpark, call it 1,000 digits. So factoring is believed to be NP intermediate. We do not know any fast algorithm for it. We definitely know algorithms that are faster than exhaustive search. And there's reasons to believe that in fact factoring should not be an NP-complete problem. We believe that this lies somewhere in between.
▶︎ 7:23 And in fact it's really important that we believe that factoring doesn't live down here. It's really important in our day to day lives that factoring does not known to have a fast algorithm, because literally every time you use your credit card to pay for something over the internet, the reason people can't steal your credit card number when you do that is because your credit card number is hidden from eavesdroppers through encryption, public key encryption. And one of the most common forms of public key encryption known as RSA encryption, in fact the security of RSA encryption actually is dependent on there not being any fast algorithm to factor numbers.
▶︎ 8:08 If someone comes up with some fast algorithm to produce factorizations of big numbers that runs quickly, actually they can totally steal your credit card information whenever you use it over the web, or more generally they can decrypt any messages people are trying to keep secret. So it's actually really important in our day to day life that we believe factoring does not live down here. But again, at the same time, we do not believe that this is an NP complete problem. We believe this is somewhere in between.
▶︎ 8:35 Let me give you one more example of a believed NP intermediate problem which will tie into a story I'll tell you in a minute, which will be graph isomorphism, which sounds kind of technical, but it's really not so bad. Graph isomorphism is a problem about networks, and it just asks if two networks are basically the same. Or at least the same up to a renaming of all of the intersections. So for example, you could imagine a network or a graph that looks like this, that's just a square. So the intersections are labeled one, two, three, four, and the roads just form a square. And you can imagine another network where again, the vertices are labeled one, two, three, four, and the roads are connected in a different pattern.
▶︎ 9:36 Now on the one hand you might say, "Well look, by visual inspection, these are not the same network." So here the roads go straight. Here the roads criss-cross. And indeed, if these were literally road networks you would not say that they are the same. But if you're thinking about these as just abstract objects representing pairwise relationships among a bunch of objects, then you would say, "Actually, these are exactly the same." These are the exact same pattern of pairwise relationships. If you just relabel these vertices three and four instead of four and three and then untangle that square, you get the square.
▶︎ 10:14 So really both of them are squares, just after a relabeling of the names of these corner points. So that's what it means for two graphs to be isomorphic, or two networks to be isomorphic. Now if there's only four different intersections, again it's not a hard problem, so you should think about what if you had a reasonably large network. So what if you had two graphs both with 1,000 intersections, is it the case you could relabel the names of one of them so that they were completely identical? That is the graph isomorphism problem that is another prime candidate for something we believe is NP intermediate. We know algorithms that are much better than exhaustive search, but we do not know any algorithms that run in polynomial time.
▶︎ 10:57 Talking about NP intermediate problems is a good opportunity for a little bit of a digression, and address a historical question that maybe was on your mind. We talked about Cook and Levin, who independently on either side of the Iron Curtain came up with the theory of NP completeness. And then we talked about how it was really Karp who, with his list of 21 NP complete problems including, for example, the TSP, it was really Karp that showed the full scope, the full impact of this theory of NP completeness. One question you might have is, arguably the hard part in some sense was the original Cook-Levin Theorem. That was the analog of Turing's original undecidability proof. Cook and Levin had to show basically from scratch that there exist NP complete problems, problems that encode every other problem with efficiently verifiable solutions. Not at all clear they should exist, and you gotta work to prove it.
▶︎ 11:54 Now once you have, just like with Turing, once Turing showed one explicit undecidable problem, he could use reductions to spread that undecidability to other problems. And that, you might remember, was the last step of the argument back in episode one. The last thing Turing did was use a reduction to spread undecidability from the initial peculiar undecidable problem that he came up with, to the one that he cared about, the halting problem. And NP-completeness actually works exactly the same way. So the Cook-Levin theorem is the thin end of the wedge. It gives you these initial NP-complete problems to start with. Once you have an NP-complete problem, you can spread NP-completeness through reductions. If you reduce one problem to another, like if you reduce one of Cook's NP-complete problems to some other problem, that shows that the latter problem is also NP-complete.
▶︎ 12:48 So really there's a big bang, which is the Cook-Levin theorem giving us that first NP-complete problem, and then we just spread that NP-completeness, reduction after reduction, after reduction, after reduction, to as many problems as we can. And Karp is really the one that carried out the second part of that research program. And so one question you might ask is, why didn't Cook or Levin just do that themselves? It almost seems like Cook and Levin did the hard part of getting the big bang, of getting the Cook-Levin theorem. Why didn't they actually go ahead and investigate all the different concrete problems that could then be proved NP-complete, like for example, the traveling salesperson problem?
▶︎ 13:28 Well, we already talked about it briefly with Cook. If I had to guess, Cook was coming, we talked about the two camps of theoretical computer scientists. We talked about the algorithms folks, the upper bound folks, and the complexity theorists, the lower bound folks, and Cook was squarely in the complexity theory camp. If I had to guess, I'd guess he thought, look, my work is done. So I just developed this new important theory. Cook did offer two concrete NP-complete problems in his paper. One, satisfiability of problem in logic, and another one, subgraph isomorphism, which is somewhat related to graph isomorphism, but NP-complete. And he stopped there. He was like, "Look, natural problems are NP-complete. If other people want to consider their own favorite problems, improve them NP-complete, go for it." My sense is that he felt that his work had been done at that point.
▶︎ 14:21 So what about Levin? Again, Levin and Cook, they weren't aware of each other's work for quite a while, because of the Cold War at the time. And Levin, I gotta tell you, Levin had some really bad luck. So Levin figured out that NP-complete problems exist, some reasonably natural ones, not as natural as the traveling salesperson problem, but some reasonably natural ones. And Levin fully recognized that his theory would be made much more interesting if he could supplement what he had with a whole bunch of compelling examples, of other problems that people had struggled with that turned out to be NP-complete. In other words, he realized that Karp's list of 21 problems would really strengthen the theory that he was developing.
▶︎ 15:07 Now here's where the bad luck came in. So I mentioned that at the time, Levin was in the Soviet Union, so initially he cut his teeth under Kolmogorov at Moscow State University, and then he developed the theory of NP-completeness at a different university. And he said to himself, "Well, what kinds of problems do my mentors care about?" Kolmogorov and other senior mathematicians in his milieu. And it turns out, according to Levin, that the senior mathematicians didn't like these puzzle type problems. Like the traveling salesperson problem and so on. That all felt a little too, I don't know, a little too shallow, to think about problems like that. So they were much more interested in more serious problems, like of an algebraic flavor. Like for example, factoring an integer and understanding the graph isomorphism problem.
▶︎ 16:01 So Levin, having literally just invented the theory of NP-completeness, and thus not really knowing anything about what the world looks like yet, there's thousands of problems in the NP-complete region, that Levin could have applied his theory to, didn't, because these were outside the aesthetic of his mentors, and somehow instead homed in on the actually seemingly much, much, much smaller set of NP-intermediate problems, and therefore didn't succeed in proving them NP-complete. So by virtue of zooming in on exactly the wrong part of NP, Levin wound up not succeeding in extending his list of NP-complete problems.
▶︎ 16:42 And so Karp meanwhile, who had spent the last, I don't know, 15, 20 years, trying to find algorithms for problems like the traveling salesman problem, he was like, "Thank you very much. I am very happy to use this theory to explain all of the problems I have failed to come up with algorithms with." So again, Karp was exactly the right person to hear about the theory of NP-completeness and recognize exactly the algorithmic problems to which it was going to apply.
▶︎ 17:09 So let's return to P versus NP, and again the question of what world do we live in? Do we live in world number one or do we live in world number two? Either way, the answer would have deep consequences. I want to talk separately through the consequences of a resolution of them being different, so a resolution putting us in world number one, and then through the ramifications of us living in world number two.
▶︎ 17:38 Suppose someone proved what most people believe, that we're in world number one, that P and NP are different, that for example, NP-complete problems cannot be solved by any fast, meaning polynomial time, algorithm. The real cynics would say like, "Oh, well, that would just be proving what we already know." But that's a terrible take. First of all, even if the outcome is sort of expected, a mathematical proof of it would be huge.
▶︎ 18:09 As an analogy, some of you might recall back in 1994 when Andrew Wiles proved, finally, Fermat's Last Theorem. And it wasn't a shock that the theorem was correct, it was a shock that Wiles was able to prove this extremely difficult deep problem that had resisted the efforts of so many brilliant mathematicians before him. Same thing here. Even if it's the expected outcome, no one's necessarily expecting a proof anytime soon. So a proof would be a big, big deal.
▶︎ 18:40 One of the reasons for that is one thing that's just almost always true about longstanding open mathematical problems like P versus NP is that, to solve it, you need to have some revolutionary mathematical ideas. So the proof itself, one would expect, would be an earthquake, the aftershocks of which would themselves lead to a large number of major advances. One expects that proving P not equal to NP would be the dam finally breaking after all of these decades, and then tons of progress would rush through after that point. So that's the first reason why a proof of P not equal to NP would be so important. Just inevitably, that would fundamentally advance mathematics, probably not just for this specific problem, but in a much broader sense as well.
▶︎ 19:29 The second reason is, honestly, talk is cheap. You can say, "Oh, sure, sure, P must not be equal to NP." But mathematics is riddled with examples of statements that everyone thought was true and turned out to be false, and vice versa. The bottom line is, sometimes the conventional wisdom is simply wrong. And as we'll discuss, the ramifications of P equal NP would be extremely important, so to verify that we're not on that timeline would be a very interesting and important thing to do.
▶︎ 20:00 And the third reason I'll mention, this is not an exhaustive list, but the third reason I'll mention is that establishing that we're in world number one, the P not equal to NP, that's basically a prerequisite for cryptography as we know it to even be possible. I introduced the factoring problem earlier. I told you how, for example, RSA encryption, the security of it rests on the assumption that factoring has no fast algorithm for it. And if you think about it, if that's actually the case, if there's no polynomial time algorithm for the factoring problem, then in fact, we must be in world one. Factoring is an NP problem.
▶︎ 20:40 You can check if someone gives you the factorization of a number. So factoring lives in this big sea of NP problems. So if we were in world number two where everything collapses, that means we'd have a fast algorithm, in particular, for factoring, and RSA encryption would be fundamentally broken. So for cryptography as we know it, and I should say, this is not merely RSA encryption. Really, in some sense, all approaches to cryptography that we're aware of require, as a prerequisite, that we're in world number one, that P is not equal to NP.
▶︎ 21:15 As you can see from this discussion, actually, you need a bit more than that. Because factoring, we do not believe to be NP-complete. So the assumption is not merely that there's some NP-complete problem that is unsolvable by fast algorithms, but there's even a specific problem in NP, namely factoring, which is not believed to be universal, and RSA encryption requires that even that specific NP problem be unsolvable by fast algorithms. So P not equal to NP doesn't mean that cryptography no longer has any existential threats, but it is a prerequisite for cryptography as we know it to be implementable. So those are some of the consequences of a proof of being in world number one, a proof that P not equal to NP, that NP-complete problems are unsolvable by fast algorithms.
▶︎ 22:04 What about the ramifications of a proof that P and NP are equal? Again, this is not the outcome that people are expecting, but we haven't ruled it out. We need to be ready for the possibility that actually, we live in world number two. In my mind, the consequences of a proof that P is equal to NP really would depend on the way in which it's proved. One case would be that the proof shows an actual practically fast algorithm that really, in the real world, very quickly solves large-scale NP-complete problems. The other possibility is that you could have just a mathematical proof, just showing a purely theoretical result, that in principle, NP-complete problems can be solved by some possibly very impractical yet polynomial time algorithm.
▶︎ 22:59 I'm going to treat those two cases separately. Let's consider the first case. Suppose not only does P equal NP in the mathematical sense, in the sense that a problem with easily recognized solutions can, at least in principle, be solved by a polynomial time algorithm. But more strongly, someone actually puts a piece of code out into the world, where anyone can download it. And if you run it, it will just very quickly sift through an astronomical number of possibilities of the traveling salesperson problem, and find you the best route from the origin to the destination.
▶︎ 23:34 Now, I've got to tell you, this is the scenario that, of all of them, I find the most unlikely. I'd be very, very surprised if in fact NP-complete problems can be solved very efficiently in a very practical sense of the word. But again, can't rule it out, so I could be wrong. But to me, this would be the most surprising one, and there'd be some good news. In some ways, this would be a huge technological breakthrough. We could use this new family of algorithms to, for any NP problem, and again, most of the problems we encounter in day-to-day life actually do have you-know-it-when-you-see-it solutions.
▶︎ 24:06 So all those problems, merely by virtue of having checkable solutions, automatically have this algorithmic shortcut, and so we can solve them extremely quickly. We can sift through big search spaces very quickly for any type of problem we want. You could drill down, for example, into medicine, and start dreaming about new applications. For example, suppose you're trying to figure out a new drug, to treat some disease. You're basically searching through this big space of possible drug designs. And all of a sudden, P equals NP in this practical algorithm, would allow you to search through that space dramatically faster than has ever been possible before.
▶︎ 24:48 Same thing with genetic interventions. The space of all genetic interventions, again, think of that as some massive search space which we historically viewed as intractably large. All of a sudden, if P equals NP, with a practical algorithm, we can search through the space of all such treatments very, very quickly. And this is just the tip of the iceberg. We could sit down and brainstorm lots of different things you would do if I literally give you a piece of code that could just zoom in through big search spaces to find exactly what you want. It would be a very, very powerful tool.
▶︎ 25:19 I guess the one piece of bad news, in this world, is that, per our previous discussion, cryptography as we know it would be dead. Pretty much any approach to encryption, like say public key encryption, you would not be able to keep messages secure if you have fast algorithms for all NP problems. And so again, this would not just break the specific approach of RSA encryption, it would not just specifically break cryptography that's based on the presumed difficulty of factoring, it would literally break basically any approach to cryptography, that is known today.
▶︎ 25:53 So perhaps the most awkward outcome could be a proof that, strictly speaking, as a mathematical statement, it is true that P and NP are the same, but maybe that is proved in a way that doesn't actually lead to any new useful algorithms. In effect, I would interpret a result like that as saying that P not equal to NP is still true in spirit, it still seems like NP-complete problems will resist any practical attempts to solve them quickly, even if P not equal to NP would be not true in letter. That's how I would interpret this scenario.
▶︎ 26:36 And this may seem hypothetical, like this may just seem like being a worrywart, and say, "No, probably one of these other two interpretable scenarios will play out." And maybe that's true, but we do actually know some specific examples. So there are some specific problems where we know them to lie in P, but the only way we know to place them in P, that is the only way we know to solve them, is with polynomial-time algorithms that are so impractical as to be unknowable.
▶︎ 27:11 So let me give you, there's even some very simple examples. Suppose I give you a network, like the road networks we were talking about when we were talking about shortest paths. And again, I want paths, but let's say I want a few different paths. So I've got a bunch of origin-destination pairs. I'm running logistics, I've got a bunch of people I need to send in different locations. And for whatever reason, I want to make sure people's paths don't overlap with each other. So they'll be known as disjoint paths in a network.
▶︎ 27:41 And suppose I just want to know, you show me a network, I have 10 origins, 10 corresponding destinations, I want to find 10 paths that don't cross each other, I want to know whether or not that's possible. Might be possible, might not be possible. Depends on the network. I just want to know which one of those two things is the case. It's definitely an NP problem. If you show me those 10 paths, I can check that they're legitimate paths, I can check that they don't cross, no problem. Definitely an NP problem.
▶︎ 28:04 Turns out, for certain classes of graphs, it's also a polynomial-time solvable problem. There exists a fast, and this time big scare quotes, "fast" algorithm, meaning polynomial-time algorithm, that checks whether or not you can find those 10 disjoint paths. This algorithm is a consequence of something known as Robertson-Seymour theory, which is quite possibly the deepest results that have ever come out of the field of graph theory. Graph theory is the part of math that thinks about networks and their structure.
▶︎ 28:42 So Robertson-Seymour theory was written about over a sequence of 20 papers that were published over more than 20 years, so literally from the early '80s to the early aughts, this is what Robertson and Seymour were doing, were developing this big, deep theory. And as a byproduct of all of their really hard math, they get a technically polynomial-time algorithm for the problem I just mentioned, for finding disjoint paths in certain classes of networks. But their algorithms, again, it's not just that they're impractically inefficient, even though they're technically polynomial-time, they're even in some sense almost unknowable. No one even really knows what that algorithm is, we just know that that algorithm exists, which does technically put that disjoint paths problem in P. So that's an example.
▶︎ 29:38 As time goes on and you start seeing some of these strange edge cases where it's like, all right, that's not really what we meant by efficient computation, but I gotta give it to you, you do satisfy the definition of a polynomial-time solvable problem. So you see that and you get a little nervous. The worry would be that that exact same thing happens not for the disjoint paths problem, which we don't believe to be NP-complete, but that the exact same thing would happen for a problem which is NP-complete. So if Robertson-Seymour theory gave us the same kind of unknowable polynomial-time algorithm for the TSP, for example, this awkward scenario is exactly where we'd be.
▶︎ 30:16 So we've always hoped, theoretical computer scientists, we've always hoped, "Oh, there are these rich edge cases with these technically polynomial time but impractical and even unknowable algorithms, hopefully that's not going to mess up this dichotomy of P versus NP-completeness that we seem to observe in the real world." Now if it did happen, if we did find ourselves in this scenario where technically P equals NP but there's no efficient algorithms that come out of the proof of that fact, personally I think the appropriate response to that result would be to revisit our definitions.
▶︎ 30:51 And in particular, basically revisit the Cobham-Edmonds thesis. Cobham and Edmonds both advocated identifying efficient computations with polynomial time. On the one hand, before you criticize a definition, it's always important to remember, critiquing from the armchair, that's what's easy. What's hard is having the courage to actually attempt a formal mathematical definition of some messy real-world concept, for example, a fast algorithm, or for example, polynomial time solvable problems as being a proxy for easy problems, or NP-complete problems as a proxy for hard problems. Any time you take a messy real-world concept and reduce it to this kind of rigid mathematical definition, at the very least, at a minimum, there'll be stuff around the edges which doesn't quite feel right. There'll be things that either should satisfy the definition but don't, or vice versa.
▶︎ 31:49 At the same time, we need heroes to be proposing good definitions to try to translate facts about the real world into math, into math so that we can do mathematics with it. We should also be interrogating every definition. We talked about this in Episode 1. We talked about the Church-Turing thesis. We said, Turing is basically equating arbitrary computations with Turing machine. This Turing machine seems really quaint. Could that really be capturing arbitrary computations? Let's interrogate that. Is there anything that Turing might have missed, for example?
▶︎ 32:23 We can do the same thing here. We can now, in this scenario, where P equals NP but we get no efficient algorithms out of the proof, we can say maybe we've been following this Cobham and Edmonds thesis for 60-plus years, but maybe we were a little too generous with our definition of a polynomial-time algorithm. Maybe that wasn't quite what we meant. Once again, you see these crazy unknowable algorithms that are technically polynomial time that fall out of, for example, Robertson and Seymour theory. Maybe it's not quite what I meant. That's your reaction. And if that's not quite what you meant, it means you need to iterate on your definitions.
▶︎ 33:02 So if polynomial time is not what you meant, if that is too permissive, if there are things that qualify as polynomial time that you do not wish to designate as efficient, then you need to come back with a revised definition, presumably a restricted subclass of polynomial-time algorithms which you feel better equates with practically realizable and efficient algorithms. In other words, you might think about restating the P not equal to NP conjecture, but with a restricted, more natural family of algorithms for which that conjecture might still be true. And if this scenario comes to pass, the good news is that actually over the last many decades, theoretical computer scientists have already been thinking a ton, a ton, about different special classes of polynomial-time algorithms. There's already a ton of ideas out there about alternative definitions that you might want to equate with efficient computation.
▶︎ 34:00 That covers the main points I wanted to make around the ramifications of a resolution of P versus NP, both the case where P is not equal to NP and the case where P equals NP. That's what I wanted to cover in the first half of this episode.
▶︎ 34:12 In the second half, I want to move on to a somewhat different question, which is to ask, how do emerging technologies challenge, if at all, all of the notions of computation that we've talked about thus far? We were just talking about interrogating definitions and how that first came up when we were discussing the Church-Turing thesis, this idea of equating Turing machines with arbitrary computations, in Episode 1. So let's revisit the assertion I made at the very beginning of this series. I said, "Computation is really not fundamentally about technology." And I said, "Imagine, you could go to some far-away planet, and there was some alien civilization, reasonably technologically advanced." And I said, "I wouldn't be surprised if the way they built their computers was different than the way we built our computers. But I would bet a ton of money that the notion of computation that they had discovered was exactly the same as ours."
▶︎ 35:09 So that's what I meant by computation transcending any specific technology. But let's push on that. A lot has happened in the 21st century so far, as far as new computing paradigms. So let's talk through how those may challenge things like the Church-Turing thesis or the extended version of it.
▶︎ 35:33 Let's start with the original Church-Turing thesis, the idea that any computation that can be expressed in any reasonable model of computation can equally be expressed as a computation carried out by a Turing machine. That's the Church-Turing thesis. So Turing machines capture everything that there is to capture. So you could ask, what's the status of the Church-Turing thesis now in 2026, 90 years after Turing's paper? And the status of the Church-Turing thesis is that it's exactly the same as it was 90 years ago. Literally, there has not been a single serious challenge to the belief encoded by the Church-Turing thesis over the past 90 years.
▶︎ 36:18 So you may find that hard to believe. For example, you might ask, "Have you ever heard of LLMs, large language models, generative AI? Aren't you aware that the world is changing rapidly around us, computers are doing all these things that we were never able to do before?" And that's true. That is definitely happening. But again, from the perspective just of computation, the computation is exactly as we have always understood it.
▶︎ 36:46 When we talk about generative AI, we usually talk about two different computations. We talk about training, machine learning training, and we talk about machine learning inference. And training is the computation you do to compute a model. So pick your favorite kind of current generative AI company, pick their latest model. That is the output of training, which is a very, very big, very, very long computation. Nonetheless, it is a computation, on standard hardware, a massive amount of standard hardware, but standard hardware.
▶︎ 37:24 Similarly, after you've computed the model, after you've done this big preprocessing step, then you do inference, and this is the part you and I experience every day when we issue a query to, for example, a large language model and it gives us a response. That's an example of inference. So that is doing a computation using the model that was computed in the training phase. But again, inference, it's just a computation. It's just an algorithm. It says given what the user typed in, and given the model, carry out the following calculations and then give back the answer.
▶︎ 38:02 So these are computations that translate utterly straightforwardly to Turing machines, because they are just computations. Again, very big, very long, very powerful computations, but computations nonetheless. They do not challenge our idea of how computations are expressed. They do not challenge the idea that Turing machines capture everything there is to be captured.
▶︎ 38:27 You say, but I also keep hearing about these quantum computers. So what's up with that? Did Turing already have in mind quantum computers? Well, I don't know the answer to that question literally, but I can tell you that any computation performed by a quantum computer can in fact be simulated by a Turing machine. There may be a blowup in the number of operations it takes, but the blowup is only finite. So any computation on a quantum computer that can be carried out in a finite number of steps can equally well be carried out on a standard Turing machine in a possibly much larger but finite number of steps.
▶︎ 39:08 So again, we said, how do you amass evidence for the Church-Turing thesis? You show that any other way of expressing computations you can think about, you can simulate those computations on a Turing machine, and exactly that type of simulation can be done with quantum computers. And so for that reason, once again, quantum computers are just in the very, very long list of ways of expressing computation which can be mapped onto Turing machine computations. So Church-Turing thesis, alive and well, as prominent as ever as it was 90 years ago.
▶︎ 39:42 What's going to be more interesting to discuss is the extended version of the Church-Turing thesis, which, to be clear, was stated by neither Church nor Turing, and so this is something that was added on by later researchers who were focusing on efficient computation. The extended Church-Turing thesis says that not only do Turing machines capture computations in any other reasonable model, but that polynomial-time Turing machines, meaning Turing machines that complete their task in a number of steps polynomial in the input size, polynomial-time Turing machines capture any other reasonable notion of efficient computation. So Turing machines being the right model not just for arbitrary computation, but also for efficient computation. That's the extended Church-Turing thesis.
▶︎ 40:33 And there is in fact a really major challenge to the extended Church-Turing thesis, to the point that most people believe that in its original form that thesis is false, and indeed that challenge to the extended Church-Turing thesis is quantum computers. Briefly, quantum computers differ from the classical computers that you and I are familiar with by taking advantage of some of the peculiarities of quantum mechanics in a way that classical computers cannot. For example, using superpositions over states, using entanglements, using interference.
▶︎ 41:07 Now, one open question is whether quantum computers are only possible in principle. It's an open question whether we can actually build in the physical world really large-scale quantum computers. Over the past five or 10 years, I have to say, there's been pretty impressive progress of making quantum computers larger and more robust and more reliable.
▶︎ 41:33 For this episode, I'm going to take the optimistic approach, and I'm going to assume that we do actually get large-scale, reliable large-scale reliable quantum computers in the next, I don't know, decade or two, something like that. Let's go ahead and assume that that's the case, and then explore the ramifications for the extended Church-Turing thesis. So why do quantum computers challenge the extended Church-Turing thesis? Well, a lot of the story here again concerns the problem of factoring.
▶︎ 42:01 Again, taking a number and decomposing it into the product of its prime factors, like 100 being equal to 2 times 2 times 5 times 5. It turns out, and this was a big, big deal when this was first proved by Peter Shor in 1994, it turns out that if you can build large-scale quantum computers, you can use them to efficiently factor large numbers. There exists an efficient quantum algorithm for factoring large numbers. And that is something we do not know how to do on a classical computer. We do not know how to do that without using the extra power given to us by quantum mechanics.
▶︎ 42:44 In fact, you recall, for decades we've actually been rather relying on the fact that classical computers cannot solve the factoring problem efficiently, because again, common methods of encryption like RSA encryption actually are only secure under the assumption that factoring is a hard problem for classical computers. At this point, you should be putting two and two together at the moment. You're kind of like, "Wait a minute, so when I send my credit card information over the web, I'm using probably something like RSA encryption, and RSA encryption is broken if there's fast algorithms for factoring, and quantum computers give you a fast algorithm for factoring." Yep. So if we can build large scale quantum computers, cryptography as it's practiced mostly today will be broken. And in particular, we will not be able to continue to send our credit card information encrypted in the same way that we do right now.
▶︎ 43:49 Quantum computers, this is one of the reasons quantum computing has been such a big deal, is because building them really does break the most common ways of doing cryptography. Now, the good news is that quantum computers, while they would break the current approaches we take to cryptographic primitives like encryption, they're not an existential threat to cryptography, or at least we don't believe so. Remember earlier I said, if P and NP collapse, if we live in world number two, then every approach we can think of to implement cryptography fails. You really need a separation between P and other problems in NP for all of the approaches we have in mind for how to do cryptography.
▶︎ 44:28 So with quantum computers, the good news is, they do not put us in world number two, or at least we don't think that quantum computers can solve NP-complete problems. Remember, factoring is not in the NP-complete region. So the fact that a quantum computer can solve factoring doesn't put us in world number two, because it's not NP-complete. It's NP-intermediate. It's totally consistent that P and NP are different, that quantum computers can't solve NP-complete problems, and that quantum computers can solve factoring. There's no contradiction there.
▶︎ 45:00 The good news is that while quantum computers would break any approach to cryptography predicated on the computational difficulty of factoring, they do not automatically break all other known approaches to having secure cryptographic systems. For example, it's all the rage in cryptography land these days to be talking about post-quantum cryptography, which means cryptographic systems which remain secure even when we have available to us large-scale quantum computers. A lot of super smart cryptographers have come up with a lot of really nice constructions for post-quantum cryptographic systems, including encryption.
▶︎ 45:39 What this means is we're still going to have cryptography even after we have quantum computers, it's just that a lot of people are going to have to do an upgrade from the old ways they were doing, for example, encryption, using RSA encryption to some of these newer methods, newer post-quantum methods, for doing encryption. And you will notice in the next decade or two, you will start noticing lots of different sites and products rolling out these upgrades to post-quantum cryptographic systems. But even if quantum computers are not an existential threat to cryptography, they are in fact an existential threat to the extended Church-Turing thesis, at least in its original form.
▶︎ 46:19 Remember, the original form of the extended Church-Turing thesis says that any efficient computation on some reasonable, physically realizable computing device, any efficient computation on any realizable device should be equally well expressed as an efficient computation on a classical Turing machine. But look, let's review what we now know to be true and/or believe. So, if factoring can be solved efficiently on a quantum computer, and again, we know that's actually true, that's what Shor proved with his algorithm back in 1994. So first of all, factoring is efficiently solvable on a quantum computer.
▶︎ 47:00 Secondly, if factoring cannot be solved efficiently, meaning in polynomial time on a classical computer, and we certainly believe that, because we bet all of e-commerce on that fact for the last multiple decades, and if large scale quantum computers can actually be physically realized, as increasingly seems likely to be the case, those three facts together literally imply that the extended Church-Turing thesis is false, is wrong. It is not the case that any efficient computation on some realizable device can be expressed as an efficient computation on a classical Turing machine. In particular, a factoring algorithm, an efficient factoring algorithm on a quantum computer cannot be equally well expressed as an efficient factoring algorithm on a classical computer, because we believe that such an algorithm does not exist.
▶︎ 47:50 So you can imagine what happened next, which was that researchers interested in computation just updated the extended Church-Turing thesis to take into account this new technology that's out there. So there's now a quantum version of the extended Church-Turing thesis, and you can guess what it says. It says, any efficient computation that can be carried out on some realizable computing device can be equally well expressed as an efficient computation on a quantum analog of a Turing machine. So a Turing machine augmented with extra capabilities to take advantage of superpositions of states, of entanglements, and of interference.
▶︎ 48:33 So that was now what people think of as the revised version, the post-quantum, if you like, version of the Extended Church-Turing Hypothesis. Any efficient computation that you're ever going to see in the real world can equally well be expressed as an efficient computation on a quantum computer. And actually to this day, so in 2026, I don't really know of any challenges, any serious challenges to this revised, this quantum-based version, of the Extended Church-Turing Hypothesis.
▶︎ 49:03 Now, we already had to revise it once, once people realized that quantum computers really were likely to be built at large scale. Maybe we have to revise it again at some point in the future, when there's some new technology. I'm not so sure that's going to be true, but we can be ready to revise it as needed if more technology comes online. So that has been the change with the new computing paradigms as far as our understanding of expressing computation. Original Church-Turing thesis, totally unchanged, totally unchallenged. The Extended Church-Turing thesis concerning efficient computations, the one change that has had to be made has been to accommodate the advent of quantum computers.
▶︎ 49:43 So finally, I want to spend some more time on a topic which I'm guessing is on your mind, it's certainly on a lot of people's minds, which is again, large language models, LLMs, and generative AI. And asking how does their amazing success challenge the way that we think about computation and its limits? And in particular, right now at least, we're in this moment in time where it seems like every month there's a new model which is substantially better than the one from last month. And so if you just extrapolate this out, you're like, wow, are we gonna hit a moment in time where literally LLMs can do absolutely anything, there'll be literally nothing that they can't do?
▶︎ 50:23 And now that I've equipped you with all this understanding of the fundamental nature of computation, you actually know the answer is no, it's not that they'll ever be able to do absolutely everything. LLMs are not going to overturn Turing's Theory of Undecidability. They're not gonna solve the halting problem, because again, undecidability is not about any specific technology. Literally any mechanical method, no matter how many resources are poured into it, fundamentally cannot solve the halting problem. And ultimately powerful as they are, generative AI are just computations, a very big, massive long computation and training to produce the model, and then computations using that model to answer users' queries in the inference stage. So no, LLMs are not going to ever fully solve the halting problem.
▶︎ 51:13 What about the P versus NP question? If at some point LLMs can just do anything that we ask them, doesn't that seem to imply that P equals NP? And again, honestly, for the same reasons, the answer is no. And in fact, unlike quantum computers, which at least challenged the extending Church-Turing thesis, generative AI doesn't even challenge the pre-quantum version, the original version of the Extended Church-Turing Thesis. They're literally just classical computations. Again, very, very big ones, but they're literally just classical computations that translate straightforwardly to a Turing machine.
▶︎ 51:50 So another way to express the point is that the development of LLMs and generative AI, they do not affect whether we live in world number one or world number two, they do not affect the answer to the P versus NP question. We're in world one or we're in world two independent of any advances in LLM technology.
▶︎ 52:11 Now that said, LLMs may wind up being very helpful for us in finally answering the question of whether we're in world one or whether we're in world two. For example, what if we're actually in world number two? What if actually P equals NP? Maybe the first person to find that algorithm, finally, that polynomial time algorithm solving some NP-complete problem, maybe that algorithm will be discovered by a very powerful LLM. In principle, a human could have discovered it, but maybe it turns out an LLM will be the first one. Or same thing, if we're in world number one, we have to prove it, we have to prove that P and NP are different, totally possible that LLMs will help us actually arrive at such a proof much more quickly than we would have otherwise.
▶︎ 52:57 So when I said they don't affect computation, I mean they don't affect the laws of the universe. They do not affect which of these worlds that we're in, but they may be very helpful for figuring out which world it is. So with this mental model of LLM and gen AI performance in mind, let me tell you about maybe the three properties of the last couple years of technological advancements that I find quite interesting and that I think are responsible for a lot of the magic that we're seeing coming out of this new technology. Some of them are more surprising than others.
▶︎ 53:35 First one, maybe the least surprising, and as you know, the amount of computation being thrown at these tasks of first of all training AI models and then just the amount of effort being put into inference, answering so many queries by so many people all over the world, completely unprecedented. This amount of computation has just literally never been thrown at a single problem before. So obviously, the more computation you throw at a problem, the better you're gonna do. That's not surprising, but it's still just been kind of amazing to watch just how much of a boost the performance of AI models have gotten through the deployment of additional computation and memory.
▶︎ 54:21 So maybe I'll summarize these three points under the title Secrets of LLM Performance. But I'll put a question mark because there's a lot going on here and I'm just teasing out three particular phenomena that I find interesting. So Secrets of LLM Performance. And what we just talked about was the massive amounts of computation, memory, et cetera. So again, not really a surprise. You throw more hardware at a problem, you're gonna do better. But man, with generative AI, boy do you do better when you throw more hardware at the problem.
▶︎ 55:18 The second point, from the perspective of the theory of computation, is perhaps the most surprising one, most surprising to me anyways. And let me call it the power of pre-processing. So the most basic version of solving a computational task is the version we've talked about thus far. Someone says, "Hey, here are two numbers to multiply," and then you multiply them and give them the answer. In some contexts, a computation gets factored into two parts, one of which is done in advance, that's the pre-processing, and then part of which is done later when you know exactly what problem you wanna solve.
▶︎ 56:14 And this idea is totally familiar to you. You open up your phone, you look at your contacts. Your contacts are not listed in chronological order. Your contacts are not listed in the order in which you added them. They are listed in alphabetical order. So that is pre-processing. Your phone does not know which contact you're going to wanna look up next, but it does this work in advance sorting your contacts so that no matter who you wanna look up, it's gonna be very quick and straightforward for you to do so.
▶︎ 56:45 So this is an age-old computational paradigm. You do work you can do upfront if possible, and then inevitably there's some work that has to wait until you know exactly the details of the task that you're supposed to carry out. Now, in terms of the theory of computation, there are definitely examples of problems where pre-processing can help, but generalizing broadly, it's often the case that pre-processing hasn't historically been seen as massively helpful. Again, sometimes you can even prove that there's not much you can do with pre-processing, because there's still so much relevant information you're only going to learn at runtime, at the time that you know exactly what problem you're supposed to solve.
▶︎ 57:29 And so what's crazy about this generation of generative AI is just how much work they're able to do in a pre-processing step. In the context of an AI model, the pre-processing is the training. So that is this massive, long computation you do, ingesting tons of data, doing all kinds of other dark art. And at the end of the day, you've got this big AI model and the most well-known models, the names you'd all recognize, they are general-purpose models, as opposed to being, for example, fine-tuned for some application domain. There are models of that type also.
▶︎ 58:06 So just like your phone, by doing the pre-processing step and sorting all of the names, it's ready for anything, totally prepared to help you look up any contact you want. That's loosely how these general-purpose AI models work. They do all this pre-processing in advance, they do all of this training so that they're ready for anything. You ask 'em whatever question you want, and they're ready to give you an answer. Answer's not always gonna be perfect, but that's the aspiration. The aspiration is you do all of this stuff in the pre-processing step, and there's very little extra to do once a user like you or me actually issues a query.
▶︎ 58:38 And to me, that's been a big surprise. It's been a surprise to me just how much productive work you can do in the pre-processing phase, and how comparably little work you can do at the inference phase, once you actually know the details of what the user is asking about.
▶︎ 58:54 That, I find, a super interesting development. I didn't necessarily expect that to be possible to this degree. And the third thing that I think is going on with the breakout performance of these latest generation of AI models, is just they've become very, very good at adapting to the types of queries that users like you and me tend to ask.
▶︎ 59:48 So let me connect what I mean back to this picture. Thinking about LLM performance, sometimes they give you an answer and it's right, sometimes they give you an answer and it's wrong, sometimes they don't give you an answer. Either they tell you they don't have an answer or they just don't complete in the desired amount of time. Now, as an AI model, on some level you're going to be wrong some of the time, you're going to not know some of the time. But there is some flexibility as far as what region here you're going to be correct on, what region you're going to be incorrect on, and what region you won't know.
▶︎ 1:00:24 So you could imagine maybe that there's one AI model where the left inputs it gets right, the middle ones it gets wrong, and the right ones, it doesn't know. You could imagine maybe there's a totally different way to do the training. Maybe there's a different dataset which results in a different AI model after training, where it slices up all of the possible inputs in a different way. And so maybe for the green AI model, maybe it's correct on the top inputs, incorrect in the middle on the equator, and then doesn't know at the bottom. So as you vary the data that you train an AI model on, it is going to be more or less accurate in different parts of the input space. Generally, it's going to be more accurate on the part of the input space where you gave it a lot of examples in the training data.
▶︎ 1:01:25 So this kind of explains why you can have, for example, for the halting problem. It might well be the case that from the user perspective, you're given the illusion as if the halting problem is solved, even when it's not. We know it's not. Halting problem is undecidable. Doesn't matter how good the generative AI is, there's going to be plenty of problems it gets wrong. But what if those are never the problems that you ask it about? Maybe the AI model is trained in a way that all of the programs you're going to wind up asking it for answers about whether they halt or not, maybe it's the green AI model and they all live up top.
▶︎ 1:02:03 So the third thing which is going on is that generative AI models, they need to be wrong some fraction of the time. That follows from undecidability in the case of the halting problem. It follows from NP-completeness in the case of something like the traveling salesman problem. They're going to be wrong or they're going to time out some fraction of the time, but they've gotten very, very good at making sure they're fast and correct in exactly the region of the input space where you and I tend to ask it questions. So that can give us the illusion of overcoming things like undecidability or NP-completeness when in fact it hasn't. It's just gotten very good at solving the sub-case of that problem in the instance space that is of interest to us.
▶︎ 1:02:45 And so I would predict what you're going to see as these models keep getting better and better, there's going to be two things that happen. So first of all, just the area of the circle, if you will, the area of the region where they can figure out the correct answer quickly, that's going to keep growing. They're just going to get better at solving the problem in more and more cases. Secondly, they're going to get even better at matching the part of the instance space that they're accurate on with the part of the instance space that you and I care about.
▶︎ 1:03:16 And so I do think as AI models keep getting better, there will be a stronger and stronger illusion that they may even be in a pragmatic sense overcoming for our immediate purposes the challenges of the halting problem or of NP-completeness. But to be clear, they are not. So even if we're never asking them about the regions of the space where they're incorrect or where they time out, those parts of the input space are still there. There are still not actually algorithms for the halting problem or efficient algorithms for the traveling salesman problem.
▶︎ 1:03:49 In closing, let me circle back from the cutting edge technology of 2026 to where we began. Computation transcends technology. It doesn't matter, at some point in the future there's data centers orbiting the earth, robot colonies on Mars. What was true in 1936 will be just as true as ever. Some tasks are fundamentally unsolvable by computer, whether it's the halting problem or determining whether or not some statement is provable.
▶︎ 1:04:25 And I don't know, hopefully maybe there's even a bit of comfort in the fact that, as rapidly as the world might be changing around us, there are nevertheless fundamental truths, laws of the universe, as it were, that will always remain exactly the same. That's all for me. I'll see you next time.