In the last episode, we discussed the most important open problem in all of computer science: the P versus NP question. At its core, this is a very deep question about the nature of computation. It asks whether easily checked solutions, as found in the Traveling Salesman Problem or in Sudoku puzzles, automatically imply the existence of algorithmic shortcuts that fast algorithms can exploit, as we see, for example, in the shortest path problem. In other words, is every NP problem, a problem with a "you-know-it-when-you-see-it" solution, also solvable by a fast algorithm?
We identify fast algorithms with algorithms that run in polynomial time: algorithms for which doubling the available computing power yields a percentage increase in the size of the problems solvable within a fixed time budget. Given this framework, we are in one of two possible worlds. If you believe Edmonds' conjecture from 1967, and accept that there is no polynomial-time algorithm for the Traveling Salesman Problem, then within the space of all NP problems, problems whose solutions can be efficiently verified when handed to you on a silver platter, there are distinct regions. There are the easy problems, like the shortest path problem, which Dijkstra's algorithm solves, and there are the hard ones, like TSP, which Edmonds, Dantzig, and Karp were all unable to solve.
Within this harder region, we can identify a special class of universal NP problems, one NP problem to rule them all, so to speak. These are the NP-complete problems. If we imagine ordering all NP problems from easiest to hardest, the NP-complete problems sit at the very top: they are at least as hard as everything else in the class, where "at least as hard as" means there exists a reduction. Every problem in NP reduces to any NP-complete problem, so solving any single NP-complete problem would solve every problem in the entire class.
This is World One, the world conjectured by Edmonds and others, corresponding to P and NP being distinct. A crucial consequence of NP-completeness is that all NP-complete problems share the same computational fate: either all of them are solvable by fast algorithms, or none of them are. World Two, by contrast, is the world in which all of them are in fact solvable by fast algorithms, the world where P equals NP. The theory of NP-completeness tells us we are definitively in one of these two worlds, but it does not tell us which one, and that remains an open mystery.
Now is as good a time as any to demystify this question: in the world where P does not equal NP, what lies in the middle? If we think about problems arranged from easier to harder, the easiest are the ones we have fast algorithms for, and the hardest are the NP-complete ones, the universal NP problems. What sits between them? These are sometimes colloquially known as NP-intermediate problems, meaning problems which are believed, on the one hand, not to be solvable by any polynomial-time algorithm, and on the other hand, not to be NP-complete, not so hard as to capture all problems with efficiently verifiable solutions.
Your first thought might be that perhaps the world admits a very simple dichotomy: every problem whose solutions can be checked efficiently is either solvable in polynomial time or NP-complete, with nothing in between. We have known since the 1970s, however, that this is not the case. A result known as Ladner's Theorem establishes that if P does not equal NP (that is, if we do not have a total collapse) then there must exist problems that fall strictly between P and the NP-complete problems. In other words, P ≠ NP implies the existence of NP-intermediate problems.
Ladner's Theorem is purely existential: it constructs a rather peculiar artificial problem which, assuming P ≠ NP, is provably neither efficiently solvable nor NP-complete. What makes this area especially interesting today is that we also have some compelling natural candidates for problems that might inhabit this intermediate region. One prominent example is factoring.
This is an important problem from the domain of number theory. Given a number, say, 100, your task is to express it as a product of primes. It turns out there is a unique way to do this: for each natural number, there is one and only one way to decompose it as a product of primes. Recall that a prime is a number whose only divisors are one and itself. For example, 100 decomposes as 2 × 2 × 5 × 5, where 2 and 5 are both prime. Factoring 100 is obviously not difficult, but imagine instead a number with, say, 1,000 digits, a very large number that we can write down, but whose factorization is far harder to find.
This is not a fabricated hypothetical. In cryptography, numbers of roughly this magnitude, on the order of 1,000 digits, are exactly what practitioners work with. Factoring is believed to be NP-intermediate: we do not know any fast algorithm for it, though we do know algorithms that are faster than exhaustive search. There are also good reasons to believe that factoring is not an NP-complete problem. The current belief is that it lies somewhere in between P and NP-complete.
It is actually critically important to our daily lives that no fast factoring algorithm is known. Every time you use a credit card to make a purchase over the internet, your credit card number is hidden from eavesdroppers through public-key encryption. One of the most widely used forms of public-key encryption, RSA encryption, has its security directly dependent on the absence of any fast algorithm for factoring large numbers. If someone were to discover such an algorithm, they could decrypt any messages people are trying to keep secret and steal credit card information whenever it is transmitted over the web.
It is therefore genuinely important, in a practical everyday sense, that factoring is not believed to lie in P. At the same time, we do not believe it is NP-complete. The prevailing view is that factoring occupies an intermediate position in the complexity landscape, somewhere strictly between the two.
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. This problem is graph isomorphism, which sounds technical but is really not so bad. Graph isomorphism is a problem about networks, and it simply asks whether two networks are essentially the same, or at least the same up to a renaming of their vertices.
For example, imagine a network that looks like a square, with vertices labeled one, two, three, and four, and edges forming that square. Now imagine a second network with the same four vertices but with the edges connected in a different pattern, so that they appear to criss-cross rather than go straight. On the surface, you might say these are not the same network, and indeed, if these were literal road networks, you would not consider them identical. But if you think of them as abstract objects representing pairwise relationships among a set of points, then they are actually exactly the same.
They represent the exact same pattern of pairwise relationships. If you simply relabel vertices three and four, swapping four and three, and then untangle the result, you recover the square. Both networks are squares; they differ only in the names assigned to their corner points. That is what it means for two graphs, or two networks, to be isomorphic.
When there are only four vertices, this is not a hard problem. But consider what happens with a reasonably large network, say, two graphs each with 1,000 vertices. The question becomes: is there a relabeling of the vertices of one graph that makes it completely identical to the other? That is the graph isomorphism problem, and it is another prime candidate for an NP-intermediate problem. We know algorithms that are far better than exhaustive search, but we do not know of any algorithm that runs in polynomial time.
Discussing NP-intermediate problems is a good opportunity for a brief historical digression. We talked about Cook and Levin, who independently, on either side of the Iron Curtain, developed the theory of NP-completeness. We then talked about how it was really Karp who, with his list of 21 NP-complete problems, including, for example, the Traveling Salesman Problem, demonstrated the full scope and impact of that theory.
One question worth asking is: arguably the hard part was the original Cook-Levin Theorem. That was the analog of Turing's original undecidability proof. Cook and Levin had to show, essentially from scratch, that NP-complete problems exist, problems that encode every other problem with efficiently verifiable solutions. It is not at all obvious that such problems should exist, and it takes real work to prove it.
Once you have that result, the situation is exactly analogous to what happened with Turing. Once Turing established one explicit undecidable problem, he could use reductions to spread undecidability to other problems. That was, if you recall, the final step of his argument: using a reduction to carry undecidability from his initial, peculiar undecidable problem to the one he actually cared about, the halting problem. NP-completeness works in exactly the same way. The Cook-Levin Theorem is the thin end of the wedge. It gives you the initial NP-complete problems to start with, and once you have even one, you can spread NP-completeness through reductions. If you reduce a known NP-complete problem to some other problem, that shows the latter is NP-complete as well.
There is, in other words, a kind of Big Bang: the Cook-Levin Theorem producing that first NP-complete problem, and then NP-completeness propagates outward, reduction after reduction, to as many problems as one can reach. Karp is really the person who carried out that second phase of the research program. Which raises a natural question: why didn't Cook or Levin do it themselves? They did the hard part. Why didn't they go on to investigate all the concrete problems that could then be proved NP-complete, such as the Traveling Salesman Problem?
In Cook's case, the answer is probably temperamental. We discussed the two broad camps in theoretical computer science: the algorithms people, focused on upper bounds, and the complexity theorists, focused on lower bounds. Cook was squarely in the complexity theory camp. My sense is that he felt his work was done. He had developed an important new theory, and he did offer two concrete NP-complete problems in his paper: satisfiability, a problem in logic, and subgraph isomorphism, which is related to graph isomorphism but is NP-complete. Having done that, his attitude seemed to be: natural problems are NP-complete; if others want to take their own favorite problems and prove them NP-complete, they are welcome to do so.
Levin's situation is more poignant: he had genuinely bad luck. Levin independently discovered that NP-complete problems exist, and identified some reasonably natural examples, though not as natural as the Traveling Salesman Problem. He fully recognized that his theory would be far more compelling if he could supplement it with a whole collection of problems that people had long struggled with and that turned out to be NP-complete. In other words, he understood that something like Karp's list of 21 problems would dramatically strengthen what he was building.
Here is where the bad luck entered. Levin was in the Soviet Union, where he had trained under Kolmogorov at Moscow State University before developing his theory of NP-completeness at another institution. When he asked himself what kinds of problems his mentors cared about, Kolmogorov and the senior mathematicians in his circle, the answer was revealing. Those mathematicians had little interest in what they regarded as puzzle-type problems: the Traveling Salesman Problem and its relatives felt, to them, too shallow to be worthy of serious attention. They were drawn instead to problems of a more algebraic character, such as integer factorization and graph isomorphism.
So Levin, having just invented the theory of NP-completeness and therefore having no map of what the landscape looked like yet, bypassed the vast and densely populated NP-complete region, which contains thousands of problems to which his theory could have been applied, and instead homed in on what turned out to be the far smaller set of NP-intermediate problems, precisely because those matched the aesthetic of his mentors. Since those problems are not NP-complete, he did not succeed in extending his list. By focusing on exactly the wrong part of NP, Levin missed the opportunity to do what Karp would later do.
Karp, meanwhile, had spent the previous fifteen or twenty years trying and failing to find efficient algorithms for problems like the Traveling Salesman Problem. When he encountered the theory of NP-completeness, his reaction was essentially one of relief and recognition: here, at last, was a framework that explained every problem he had failed to crack. He was precisely the right person to receive the theory and to see immediately which algorithmic problems it was going to illuminate.
Let's return to the P versus NP question, and specifically to the question of which world we live in. Either resolution would carry deep consequences, so it's worth examining them separately, first the ramifications of proving that P and NP are different, and then those of discovering we live in world number two.
Suppose someone proved what most people believe: that we are in world number one, that P and NP are different, and that NP-complete problems cannot be solved by any polynomial-time algorithm. The cynics might say, "That would just be proving what we already know." But that is a terrible take. Even when an outcome is expected, a mathematical proof of it would be enormous. Consider the analogy of Andrew Wiles proving Fermat's Last Theorem in 1994. It was not a shock that the theorem was correct; it was a shock that Wiles had managed to prove an extraordinarily difficult problem that had resisted the efforts of so many brilliant mathematicians before him. The same logic applies here: even if a proof of P ≠ NP confirms the expected outcome, no one is necessarily expecting such a proof anytime soon, and its arrival would be a very big deal.
One reason for that is almost universally true of longstanding open mathematical problems: to solve them, you need revolutionary ideas. The proof itself would be an earthquake, the aftershocks of which would drive a large number of major advances. Proving P ≠ NP would be the dam finally breaking after decades of effort, with a flood of progress rushing through afterward. Such a proof would inevitably advance mathematics in a fundamental way, not just for this specific problem, but in a much broader sense as well.
The second reason is that talk is cheap. One can assert that P must not equal NP, but mathematics is riddled with examples of statements everyone believed to be true that turned out to be false, and vice versa. The conventional wisdom is sometimes simply wrong. Given how important the ramifications of P = NP would be, verifying that we are not on that timeline would itself be a significant and important achievement.
The third reason (and this is not an exhaustive list) is that establishing we are in world number one is essentially a prerequisite for cryptography as we know it to be possible. Recall the factoring problem and the fact that the security of RSA encryption rests on the assumption that factoring has no fast algorithm. Factoring is an NP problem: given a proposed factorization of a number, you can verify it efficiently. So factoring lives within the broad class of NP problems. If we were in world number two, where everything collapses, we would have a fast algorithm for factoring in particular, and RSA encryption would be fundamentally broken.
This point extends well beyond RSA. In some sense, all approaches to cryptography that we are currently aware of require, as a prerequisite, that we are in world number one, that P ≠ NP. As this discussion makes clear, one actually needs a bit more than that. Factoring is not believed to be NP-complete, so the relevant assumption is not merely that some NP-complete problem is unsolvable by fast algorithms, but that even this specific problem in NP, one not believed to be universal, is unsolvable by fast algorithms. A proof of P ≠ NP would therefore not eliminate all existential threats to cryptography, but it is a necessary prerequisite for cryptography as we know it to be implementable at all.
What are the ramifications of a proof that P equals NP? This is not the outcome most researchers are expecting, but it has not been ruled out, so we need to be prepared for the possibility that we live in that world. The consequences of such a proof would depend critically on the manner in which it is proved. One case would be a proof that exhibits an actual, practically fast algorithm, one that genuinely solves large-scale NP-complete problems quickly in the real world. The other possibility is a purely mathematical proof establishing, in principle, that NP-complete problems are solvable in polynomial time by some algorithm that may be entirely impractical. These two cases deserve to be treated separately.
Consider the first case. Suppose that not only does P equal NP in the mathematical sense, meaning that problems with easily verified solutions can in principle be solved in polynomial time, but that someone actually releases working code into the world. Anyone can download it, run it, and watch it sift through an astronomical number of possibilities for, say, the Traveling Salesman Problem, returning the optimal solution very quickly. This is, of all the possible outcomes, the most surprising one. It would be an extraordinary technological breakthrough, because the vast majority of problems we encounter in everyday life have solutions that are easy to verify once found. All such problems would automatically admit this algorithmic shortcut, allowing us to search through enormous spaces with remarkable speed.
To make this concrete, consider drug discovery. Designing a new drug to treat a disease is fundamentally a search through a vast space of possible molecular structures. A practically fast algorithm for NP-complete problems would allow us to search that space dramatically faster than has ever been possible. The same applies to genetic interventions: the space of all possible treatments, historically viewed as intractably large, would suddenly become navigable. These are just two examples; one could brainstorm many more applications of a tool that can zoom in on exactly what you want within an enormous search space.
There is, however, one significant piece of bad news in this scenario. As discussed previously, cryptography as we know it would be destroyed. A practically fast algorithm for NP problems would not merely break RSA encryption or cryptographic schemes based on the presumed difficulty of factoring; it would break essentially every approach to encryption known today, including public-key cryptography in general. Keeping messages secure would become impossible.
Perhaps the most awkward possible outcome would be a proof that, strictly speaking, P and NP are the same, but proved in a way that yields no new useful algorithms. I would interpret such a result as saying that P ≠ NP is still true in spirit — NP-complete problems would still resist any practical attempt to solve them quickly — even if P ≠ NP were false in the letter of the law.
This may seem like an overly hypothetical worry, but we actually have concrete examples of problems that lie in P yet whose only known polynomial-time algorithms are so impractical as to be almost unknowable. Consider a simple illustration: suppose you are given a road network and a collection of ten origin-destination pairs — say, you are running a logistics operation and need to route ten different parties to ten different locations. For whatever reason, you want the routes to be vertex-disjoint, meaning no two paths share a node. You simply want to know whether such a set of disjoint paths exists. This is clearly in NP, since if someone hands you ten candidate paths you can immediately verify that they are valid and pairwise disjoint.
It turns out that, for certain classes of graphs, this problem is also polynomial-time solvable — but the algorithm that places it in P is a consequence of Robertson–Seymour theory, quite possibly the deepest body of results ever produced in graph theory. Robertson and Seymour developed this theory across a sequence of roughly twenty papers published over more than twenty years, from the early 1980s through the early 2000s. As a byproduct of that extraordinarily deep mathematics, one obtains a technically polynomial-time algorithm for the disjoint paths problem. Yet the algorithm is not merely impractical — it is, in a meaningful sense, unknowable: we know the algorithm exists, but no one can really write it down explicitly.
As you encounter strange edge cases like this, you begin to feel a certain unease. The worry is that exactly the same thing could happen not for the disjoint paths problem, which we do not believe to be NP-complete, but for a problem that is NP-complete. If Robertson–Seymour theory had instead delivered the same kind of unknowable polynomial-time algorithm for the Travelling Salesman Problem, for example, we would find ourselves squarely in this awkward scenario.
Theoretical computer scientists have always hoped that these rich edge cases — technically polynomial-time but wholly impractical and unknowable algorithms — would not disturb the clean P-versus-NP-completeness dichotomy we observe in practice. If we did find ourselves in this scenario, where technically P equals NP but no useful algorithm emerges from the proof, the appropriate response, in my view, would be to revisit our definitions entirely.
This brings us to a reconsideration of the Cobham-Edmonds thesis. Both Cobham and Edmonds advocated identifying efficient computation with polynomial time. Before criticizing that definition, it is important to remember that critiquing from the armchair is easy. What is hard is having the courage to attempt a formal mathematical definition of some messy real-world concept — for example, what it means for an algorithm to be fast, or for polynomial-time solvability to serve as a proxy for tractability, or NP-completeness to serve as a proxy for hardness. Any time you reduce a messy real-world concept to a rigid mathematical definition, there will inevitably be things around the edges that do not feel quite right: cases that should satisfy the definition but do not, or cases that satisfy it but arguably should not.
At the same time, we need the heroes who propose these definitions — who translate facts about the real world into mathematics so that we can reason about them rigorously. We should also be interrogating every definition. We saw this in Episode 1 when we examined the Church-Turing thesis: Turing equates arbitrary computation with Turing machines, and we asked whether that seemingly quaint model could really capture all possible computations, and whether Turing might have missed anything. We can apply exactly the same scrutiny here.
In the scenario where P equals NP but the proof yields no practically useful algorithms, one natural reaction is that we may have been too generous with our definition of a polynomial-time algorithm — that it does not quite capture what we meant. Consider the strange, unknowable algorithms that emerge technically as polynomial-time from results such as the Robertson-Seymour graph minor theory. The instinctive response is that this is not really what efficiency was supposed to mean. That reaction is a signal that the definition needs to be refined.
If polynomial time is too permissive — if there are algorithms that qualify as polynomial-time yet should not be designated as efficient — then the right response is to return with a revised definition: a restricted, more natural subclass of polynomial-time algorithms that better captures the notion of practically realizable efficiency. In other words, one might restate the P ≠ NP conjecture using this tighter family of algorithms, for which the conjecture might still hold even if it fails for the broader class. The encouraging news is that theoretical computer scientists have already spent many decades thinking deeply about exactly such special classes of polynomial-time algorithms, so there is already a rich body of ideas about alternative definitions one might adopt.
That covers the main points I wanted to make about the ramifications of a resolution of the P versus NP question — both the case where P is not equal to NP and the case where P equals NP. That concludes the first half of this episode.
In this second half, I want to move on to a somewhat different question: how do emerging technologies challenge, if at all, the notions of computation we have discussed thus far? This question first came up when we were discussing the Church-Turing thesis — the idea of equating Turing machines with arbitrary computation — back in Episode 1. So let's revisit the assertion I made at the very beginning of this series: computation is not fundamentally about technology.
Imagine traveling to some distant planet inhabited by a reasonably advanced alien civilization. I would not be surprised if the way they built their computers was quite different from the way we build ours. But I would bet a great deal of money that the notion of computation they had discovered was exactly the same as ours. That is what I mean by computation transcending any specific technology.
With that in mind, let's push on that claim. A great deal has happened in the twenty-first century in terms of new computing paradigms, so let's examine how those developments may challenge things like the Church-Turing thesis or its extended version. The Church-Turing thesis holds that any computation expressible in any reasonable model of computation can equally be expressed as a computation carried out by a Turing machine — that Turing machines capture everything there is to capture.
What is the status of the Church-Turing thesis now, in 2026, ninety years after Turing's paper? It is exactly the same as it was ninety years ago. There has not been a single serious challenge to the belief encoded by the Church-Turing thesis over the past nine decades. You might find that hard to believe. You might ask whether large language models, generative AI, and the rapid transformation of what computers can do constitute such a challenge. They do not — at least not from the perspective of computation itself.
When we discuss generative AI, we are really discussing two distinct computations: training and inference. Training is the computation performed to produce a model — a very large, very long computation, but a computation nonetheless, running on standard hardware, albeit a massive amount of it. Inference is what you and I experience every day when we issue a query to a large language model and receive a response: given the user's input and the trained model, carry out the specified calculations and return an answer.
Both training and inference translate straightforwardly to Turing machines, because they are simply computations — very large, very long, and very powerful, but computations nonetheless. They do not challenge our understanding of how computations are expressed, and they do not challenge the idea that Turing machines capture everything there is to capture.
You might also ask about quantum computers. Did Turing already have quantum computers in mind? I cannot answer that literally, but I can tell you that any computation performed by a quantum computer can be simulated by a Turing machine. There may be a blowup in the number of operations required, but that blowup is only finite. Any computation a quantum computer can carry out in a finite number of steps can equally be carried out on a standard Turing machine in a possibly much larger, but still finite, number of steps.
Recall how we amass evidence for the Church-Turing thesis: we show that any other way of expressing computation we can conceive of can be simulated on a Turing machine. Exactly that kind of simulation can be done with quantum computers. For that reason, quantum computers join the very long list of computational models that can be mapped onto Turing machine computations. The Church-Turing thesis remains alive and well, as prominent as it was ninety years ago.
The next topic to discuss is the extended Church-Turing thesis, which, to be clear, was stated by neither Church nor Turing. It was added later by researchers focused on efficient computation. The extended Church-Turing thesis asserts that not only do Turing machines capture computation 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 — capture any other reasonable notion of efficient computation. In other words, Turing machines are the right model not just for arbitrary computation, but for efficient computation as well.
There is in fact a major challenge to the extended Church-Turing thesis, to the point that most researchers believe the thesis, in its original form, is false. That challenge comes from quantum computers. Quantum computers differ from the classical computers we are familiar with by exploiting peculiarities of quantum mechanics that classical computers cannot, such as superpositions over states, entanglement, and interference.
One open question is whether large-scale quantum computers are only possible in principle, or whether we can actually build them in the physical world. Over the past five to ten years, there has been impressive progress in making quantum computers larger, more robust, and more reliable. For the purposes of this discussion, I will take the optimistic view and assume that large-scale, reliable quantum computers become available within the next decade or two, then explore the ramifications for the extended Church-Turing thesis.
With that assumption in place, why exactly do quantum computers challenge the extended Church-Turing thesis? Much of the story here again concerns the problem of factoring.
Factoring means decomposing a number into the product of its prime factors — for example, 100 equals 2 × 2 × 5 × 5. It turns out — and this was a landmark result when Peter Shor first proved it in 1994 — 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, and that is something we do not know how to do on a classical computer; we do not know how to do it without the extra power given to us by quantum mechanics.
For decades, we have actually been relying on the fact that classical computers cannot solve the factoring problem efficiently. Common methods of encryption such as RSA encryption are only secure under the assumption that factoring is hard for classical computers. Putting these two facts together: when you send your credit card information over the web, you are likely using something like RSA encryption; RSA encryption is broken if there exist fast algorithms for factoring; and quantum computers provide exactly such a fast algorithm. Therefore, if we can build large-scale quantum computers, cryptography as it is practiced today will be broken, and we will not be able to continue encrypting sensitive information in the same way we currently do.
The good news is that quantum computers, while they would break our current approaches to cryptographic primitives like encryption, are not an existential threat to cryptography — or at least we do not believe they are. Recall that if P and NP collapse, every approach we can think of to implement cryptography fails, because all of our known approaches require a separation between P and problems in NP. Quantum computers do not put us in that world, because we do not believe quantum computers can solve NP-complete problems.
Critically, factoring is not in the NP-complete region — it sits in the NP-intermediate region. The fact that a quantum computer can solve factoring therefore does not collapse P and NP. It is entirely consistent that P and NP are different, that quantum computers cannot solve NP-complete problems, and that quantum computers can solve factoring. There is no contradiction.
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 building secure cryptographic systems. It is very much in vogue in cryptography today to discuss post-quantum cryptography — cryptographic systems that remain secure even when large-scale quantum computers are available. A great many brilliant cryptographers have developed impressive constructions for post-quantum cryptographic systems, including encryption schemes.
What this means in practice is that we will still have cryptography after quantum computers arrive; it is simply that a large number of people and organizations will need to upgrade from older methods — such as RSA encryption — to these newer post-quantum methods. Over the next decade or two, you will begin to notice many different sites and products rolling out exactly these upgrades to post-quantum cryptographic systems.
Even if quantum computers are not an existential threat to cryptography, however, they are very much an existential threat to the extended Church–Turing thesis, at least in its original form.
Recall that the original form of the Extended Church-Turing Thesis asserts that any efficient computation on some physically realizable computing device can equally well be expressed as an efficient computation on a classical Turing machine. Let us review what we now know, or strongly believe, to be true. First, factoring can be solved efficiently on a quantum computer — that is precisely what Shor proved with his algorithm in 1994. Second, we believe that factoring cannot be solved efficiently, meaning in polynomial time, on a classical computer; we have, after all, staked the security of e-commerce on that belief for several decades. Third, large-scale quantum computers can actually be physically realized, as increasingly seems to be the case.
Those three facts together literally imply that the Extended Church-Turing Thesis is false. It is not the case that every efficient computation on some realizable device can be expressed as an efficient computation on a classical Turing machine. In particular, an efficient factoring algorithm running on a quantum computer cannot be equally well expressed as an efficient factoring algorithm on a classical computer, because we believe no such classical algorithm exists.
What happened next is that researchers updated the Extended Church-Turing Thesis to account for this new technology. There is now a quantum version of the thesis, and its content is easy to anticipate: any efficient computation that can be carried out on some physically realizable device can equally well be expressed as an efficient computation on a quantum analog of a Turing machine — that is, a Turing machine augmented with the ability to exploit superpositions of states, entanglement, and interference. This is now the revised, post-quantum version of the Extended Church-Turing Thesis.
As of 2026, I am not aware of any serious challenges to this quantum-based revision. Of course, we already had to revise the thesis once, when it became clear that large-scale quantum computers were likely to be built. It is possible we will need to revise it again if some further new technology emerges, though I am not convinced that will prove necessary. We should simply remain prepared to update our understanding as new computing paradigms arise.
To summarize the overall picture: the original Church-Turing Thesis concerning what is computable remains entirely intact and unchallenged. The Extended Church-Turing Thesis concerning efficient computation has required exactly one revision — to accommodate the advent of quantum computers.
I want to spend some time on a topic that is certainly on a lot of people's minds: large language models, LLMs, and generative AI — and specifically, how their remarkable success challenges the way we think about computation and its limits. We are in a moment where it seems as though every month brings a new model substantially better than the one before it. If you simply extrapolate that trend, you might wonder whether we will eventually reach a point where LLMs can do absolutely anything.
Now that you have a solid understanding of the fundamental nature of computation, you actually know the answer: no. LLMs are not going to overturn Turing's theory of undecidability. They are not going to solve the halting problem, because 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. Powerful as they are, generative AI systems are just computations — a very large, long computation during training to produce the model, and then further computations during inference to answer users' queries.
What about the P versus NP question? If LLMs could eventually do anything we asked of them, doesn't that seem to imply that P equals NP? Again, for essentially the same reasons, the answer is no. Unlike quantum computers, which at least challenge the extended Church-Turing thesis, generative AI does not even challenge the pre-quantum, original version of that thesis. These systems are literally classical computations — very large ones, but classical computations that translate straightforwardly to a Turing machine.
Another way to express the point is that the development of LLMs and generative AI does not affect whether we live in world one or world two. It does not affect the answer to the P versus NP question. We are in world one or we are in world two entirely independent of any advances in LLM technology.
That said, LLMs may turn out to be very helpful in finally answering the question of which world we inhabit. If we are actually in world two — if P equals NP — perhaps the first person to discover a polynomial-time algorithm for some NP-complete problem will not be a person at all, but a powerful LLM. A human could in principle have found it, but an LLM might get there first. Equally, if we are in world one and must prove that P and NP are different, it is entirely possible that LLMs will help us arrive at such a proof far more quickly than we would have otherwise. So when I say LLMs do not affect computation, I mean they do not affect the laws of the universe or which of these worlds we actually inhabit — but they may be enormously helpful in figuring out which world it is.
With that mental model of LLM and generative AI performance in place, let me describe what I consider the three most interesting properties of the technological advances of the last couple of years — properties that I believe are responsible for much of the remarkable capability we are seeing from this new technology. Some of these are more surprising than others. The first, and perhaps the least surprising, is —
The amount of computation being thrown at the tasks of training AI models, and then the sheer volume of effort devoted to inference—answering queries from so many people all over the world—is completely unprecedented. This amount of computation has literally never been directed at a single problem before. Obviously, the more computation you throw at a problem, the better you are going to do; that is not surprising. But it has still been remarkable to watch just how much of a boost AI model performance has received through the deployment of additional computation and memory.
With that as a first point, let me turn to what I would call the power of pre-processing—and from the perspective of the theory of computation, this is perhaps the most surprising phenomenon of the three. The most basic version of solving a computational task is the one we have discussed thus far: someone asks you to multiply two numbers, you multiply them and return the answer. In some contexts, however, a computation gets factored into two parts: one done in advance, the pre-processing, and one done later, once you know exactly what problem you need to solve.
This idea is entirely familiar. When you open your phone and look at your contacts, they are not listed in the order you added them—they are listed alphabetically. That is pre-processing. Your phone does not know which contact you will want to look up next, but it does the sorting work in advance so that, no matter who you want to find, the lookup is quick and straightforward. This is an age-old computational paradigm: do the work you can do upfront, and leave for runtime only the work that must wait until you know the exact details of the task.
In the theory of computation, there are certainly examples of problems where pre-processing helps, but broadly speaking, it has not historically been seen as massively helpful. In many cases one can even prove that pre-processing cannot accomplish much, because so much relevant information only becomes available at runtime, when you finally know exactly what problem you are supposed to solve. What is remarkable about this generation of generative AI is just how much work these models are able to accomplish in the pre-processing step.
In the context of an AI model, the pre-processing is the training: a massive, extended computation that ingests enormous quantities of data and performs all manner of additional work. At the end of it, you have a large AI model. The most well-known, general-purpose models—as opposed to those fine-tuned for a specific application domain—are, in this respect, analogous to your phone's sorted contact list: by doing the pre-processing in advance, they are ready for anything. You can ask whatever question you want, and they are prepared to give you an answer.
The aspiration is that virtually all of the productive work happens in the pre-processing phase, leaving very little extra to do once a user actually issues a query. To me, that has been a genuine surprise—just how much useful work can be accomplished during training, and how comparably little needs to happen at inference time, once you actually know the details of what the user is asking.
A third factor behind the breakout performance of the latest generation of AI models is that they have become very good at adapting to the types of queries that users like you and me tend to ask. To understand what this means, consider how LLM performance can be mapped across the space of all possible inputs. Sometimes a model gives you a correct answer, sometimes an incorrect one, and sometimes it gives no answer at all — either explicitly declining or failing to complete in the desired time. Any AI model will be wrong some fraction of the time and unable to answer some fraction of the time, but there is flexibility in which regions of the input space fall into each category.
Imagine one AI model that gets the left portion of the input space correct, the middle portion wrong, and the right portion unknown. A different model, trained on a different dataset, might slice up the input space entirely differently — correct on the top inputs, incorrect in the middle, and unknown at the bottom. In general, a model tends to be more accurate on the parts of the input space where it was given many training examples. This explains how, from a user's perspective, one can be given the illusion that something like the halting problem has been solved, even when it has not.
We know the halting problem is undecidable. No matter how capable a generative AI model is, there will always be programs it answers incorrectly. But what if those programs are never the ones you happen to ask about? If the model has been trained such that all the programs users actually query about happen to fall in the region where the model is fast and correct, then from the user's perspective the problem appears solved. The same logic applies to NP-complete problems like the traveling salesman problem: the model will be wrong or will time out on some fraction of inputs, but it has become very good at ensuring that fraction does not overlap with the inputs that users typically care about.
Looking ahead, I expect two things to happen as these models continue to improve. First, the region of the input space where they produce correct answers quickly will keep expanding — they will simply get better at solving more cases. Second, they will get even better at aligning the region where they are accurate with the region that users actually care about. This will create an increasingly strong illusion that AI is, in some pragmatic sense, overcoming the fundamental challenges posed by undecidability or NP-completeness.
To be clear, however, that illusion is not the reality. Even if we never ask about the regions of the input space where the model is incorrect or times out, those regions still exist. There are still no algorithms for the halting problem, and there are still no efficient algorithms for the traveling salesman problem.
To close, let me circle back from the cutting-edge technology of 2026 to where we began: computation transcends technology. It does not matter whether, at some point in the future, there are data centers orbiting the earth or 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 is the halting problem or determining whether a given mathematical statement is provable.
Perhaps there is even a measure of comfort in that fact. As rapidly as the world changes around us, there are nevertheless fundamental truths — laws of the universe, as it were — that will always remain exactly the same.