My name is Tim Roughgarden, and I will be your guide for this series on Computation and Its Limits. These may sound like topics that are fundamentally about computers and technology, and superficially they are. On a deeper level, however, they are not. They are concepts that transcend any specific technology; they concern fundamental properties of the universe we live in, laws of nature in effect.
In each of the five episodes in this series, we will grapple with some of these fundamental concepts and questions.
In the first episode, we are going to ask: is there anything computers can't do? They seem so powerful, and ever more powerful with every month that goes by. To reason about that question, we need a model of what it is computers can actually do. I will introduce you to a famous such model known as the Turing machine.
Drawing on ideas ranging from universality, to simulation, to diagonalization, to reductions, we will work through Turing's original argument that there are problems, even natural problems you would genuinely like to solve, that are fundamentally unsolvable by computers. The most famous such problem is the halting problem, and "fundamentally unsolvable" means not merely today, but as far into the future as you care to think about.
In this episode, we examine a few examples of the kinds of algorithmic shortcuts that very clever algorithms take advantage of. In many cases, these are algorithms that form the basis of technology we use every day. If you have ever wondered how your favorite map application computes driving directions, that is one example of technology built on clever algorithmic shortcuts.
For an even more basic example, consider the act of multiplying two numbers together, something we all learned a method for back in grade school. Depending on what kind of student you were at the time, you may or may not have asked: "I understand that this is a way to multiply two numbers together, but is it the best way? Could there be something better? Could you arrive at the same answer with less work?"
We are going to ask exactly that question in this episode, and we will see that the answer is, in fact, yes. We will examine a famous algorithm known as Karatsuba multiplication, whose clever idea is to expose the redundant work hidden inside the standard method and reuse it, thereby arriving at a faster algorithm. This will serve as one striking example of the remarkably ingenious things that algorithms are able to do.
In this episode, we focus on two crucial concepts: our current understanding of what makes a computational task easy, and the dichotomy between those easy problems, problems that can be solved quickly by a computer, and a second category of problems that appear to be fundamentally unsolvable by fast algorithms.
There is no obvious reason to expect this, yet modern computer science has revealed a startling fact: many problems that look entirely different from one another, routing traffic, scheduling tasks, solving puzzles, and countless others, turn out to have exactly the same computational complexity. That is, the difficulty of carrying out these seemingly unrelated computational tasks is identical. These problems, despite their different appearances, are really just thinly disguised versions of the exact same underlying problem.
As a consequence, for the many computational tasks where we have not yet found efficient solutions, this failure appears to reflect not a lack of ingenuity on our part, but rather a structural feature of computation itself.
We will do a deep dive on the most important open question in all of computer science, and one of the most important open questions in all of mathematics, known as the P versus NP question. This concerns the dichotomy of problems we will cover in the third episode: the easy problems solvable by fast algorithms, and the hard problems that, as far as we can tell, appear to be unsolvable by fast algorithms.
The P versus NP question asks whether this dichotomy is fundamental, or whether it might collapse entirely. Put another way, it asks whether algorithmic shortcuts, like the ones used by your map application for driving directions, are everywhere, or whether they are unique to specific problems. That question will be taken up in the final episode.
In this fifth episode, we begin by discussing the ramifications of the P versus NP question. We don't know the answer to that question, perhaps P equals NP, perhaps P differs from NP, so we'll work through the implications of each scenario. Once we've done that, we'll wrap up the series by pondering a broader question: do new computational paradigms change our understanding of what "solvable," or "efficiently solvable," actually means?
Current technology trends have produced developments that, at least superficially, appear to outperform the conventional expectations we hold for computers. Quantum computing, powerful optimization solvers such as integer programming systems, and large language models, generative AI, all fall into this category. The question, then, is whether we need to revisit everything covered in the preceding episodes.
Do these technological developments undermine traditional notions of efficient computation, or do they leave the deeper limits intact? What survives when our best abstractions are stress-tested by new technology? That is how we'll bring the series to a close.
To help you assess whether you'd enjoy spending some time with the rest of this series, let me close this introductory video with a top ten list of highlights, a sample of what we'll be covering.
In case you thought Alan Turing was just a code breaker, in case you know him only for the work he did at Bletchley Park during World War II, you will learn that Turing is in fact responsible for authoring the paper that many computer scientists, myself included, regard as the birth of our discipline: the birth of computer science as an intellectual discipline.
You might come for Alan Turing, but you should stay for the full cast of characters, one that includes many of the most famous mathematicians and computer scientists of the 20th century. Names like David Hilbert, Kurt Gödel, John von Neumann, George Dantzig, Andrei Kolmogorov, Jack Edmonds, Stephen Cook, Leonid Levin, Richard Karp, and Don Knuth will all appear in the stories we have to tell, sometimes in major roles and sometimes in cameos.
For the next two items on the top ten list, we will explore two very surprising and unexpected facts about computation. First, if you take some objective you would like an algorithm to carry out, it turns out that very small changes to the nature of the task can have massive implications for how easy or difficult that task is. Two problems can look almost identical, and yet one can be extremely easy to solve while the other can be extremely difficult.
On the other hand, while near-identical problems can behave very differently, very different-looking problems can sometimes behave almost identically. There is a whole range of problems that look nothing like each other, and yet all of them turn out to be thinly disguised versions of the exact same problem. That is the essence of the theory of NP-completeness, which we will discuss next.
You will learn why the multiplication method you studied in grade school is not optimal, in the sense that it will take you longer to compute the product of two numbers using the grade-school algorithm than if you use something called Karatsuba's method.
As part of the cast of characters who appear in this story, it is almost impossible, when discussing mathematical history, to avoid the peculiarities of mathematicians, both as individuals and as a community. With that in mind, let us turn to some funny mathematician stories.
Another topic we will explore, as a byproduct of some of the other historical developments covered in this course, is computer science's fight for recognition and respect. Once upon a time, computer science was not recognized as a serious intellectual discipline. That only began to change in the 1960s, gained further momentum in the 1970s and 1980s, and by the 1990s had finally reached a point where virtually every university agreed it deserved its own department. By the end of the twentieth century that recognition was universal, but it was not always an easy road to travel.
We will therefore be tracing the story of computer science's establishment as its own deep intellectual discipline, one worthy of the same standing as mathematics, physics, or any of the other sciences.
How do all of these ideas from the last 90 years connect to the technological developments we are seeing today in 2026? Large language models, generative AI: these seem to be changing everything around us. Yet for the topics we will be discussing in this series, for the nature of computation and its limits, they change nothing.
Another major technological development you may be hearing a lot about is quantum computers. People are working very hard right now to build bigger and more reliable quantum computers. This does change our notion of efficient solvability to some extent, and we will discuss that. But even if we succeed in building large-scale quantum computers, it really does not change the nature of computation or its fundamental limits as much as you might think.
Finally, number one has to be the P versus NP question. Throughout this series, you will come to understand at a reasonably deep level exactly what this most important open question in computer science, and one of the top open questions in all of mathematics, is asking. You will have a sense of what the question means mathematically, why it is so important, and why it has eluded the efforts of so many of the most brilliant minds of the past half-century.
Informally, the P versus NP question asks whether every problem for which you can easily recognize solutions must also have an efficient algorithm for finding them. Consider Sudoku: if someone shows you an alleged solution, it is very easy to check whether it follows all the rules. The question is whether this "you know it when you see it" character of solutions, not just for Sudoku, but for literally any such problem, guarantees the existence of an algorithmic shortcut. In other words, must every problem with efficiently verifiable solutions also have an efficient algorithm for solving it?
Alternatively, it may be the case that some problems, Sudoku, the Traveling Salesperson Problem, and many other famous examples, are fundamentally beyond the reach of efficient computation, even though their solutions are easy to verify. That is the P versus NP question, which we will explore at length. It is a remarkable list of topics, and I hope you are as excited as I am. If you are, I will see you in episode one.