▶︎ 0:00 Hi, everyone. My name is Tim Roughgarden, and I'm going to be your guide for this series on Computation and its Limits. Those may sound like topics that are fundamentally about computers and technology, computation and its limits, and superficially, they are. But, as we'll see, on a deeper level, really, they're not.
▶︎ 0:23 Really, they're concepts that transcend any specific technology. They're about fundamental properties of the universe that we live in, really laws of nature, in effect.
▶︎ 0:35 In each of the five episodes in this series, we're going to grapple with some sort of fundamental concepts and questions. In the first episode, we're going to ask, is there anything computers can't do? They seem so powerful, ever more powerful with every month that goes by. To reason about that question, is there anything computers can't do, we're going to need to have a model of what it is computers can do.
▶︎ 1:00 I'm going to introduce you to a famous such model known as a Turing machine. And then in that same first episode, I'm going to draw on ideas ranging from universality, to simulation, to diagonalization, to reductions, to show you Turing's original argument that indeed, there are problems, even natural problems you'd really like to solve, like the famous one being the halting problem, which are fundamentally, meaning both today and as far into the future as you care to think about, that are fundamentally unsolvable by computers.
▶︎ 1:34 In the second episode, we're going to examine a few examples of the kinds of algorithmic shortcuts which very clever algorithms take advantage of, in many cases, algorithms that form the basis of technology that we use every day. If you've ever wondered how your favorite map application computes driving directions for you, that would be one example of technology based on clever algorithmic shortcuts. And for an even more basic example, think about just literally multiplying two numbers together, something we all learned a method for back in grade school.
▶︎ 2:12 And depending on what kind of third grader or fourth grader or whatever you were, you may or may not have asked at that time, "Huh, okay, I get that this is a way to multiply two numbers together, but is it the best way to multiply two numbers together?" Could there be something better? Could you arrive at the same answer with less work? Maybe you never asked that question at the time, but we're going to ask it in the second episode of this series, and we're actually going to see that the answer is, in fact, yes.
▶︎ 2:42 I'm going to show you a famous algorithm known as Karatsuba's multiplication algorithm, where the clever idea is to basically expose redundant work, and the usual way you multiply two numbers, the one you learned, expose redundant work, and instead reuse it, thereby arriving at a faster algorithm. So that will be one example that we'll see of the mind-bogglingly clever things that algorithms are able to do.
▶︎ 3:08 In the third episode, we're going to focus on two really, really crucial concepts, our current understanding of what it is that makes a computational task easy, and the dichotomy between those easy problems, problems that can be solved quickly by computer, and a second category of problems which appear to be difficult, which appear to be fundamentally unsolvable by fast algorithms.
▶︎ 3:37 In fact, this is something there's no reason to expect that this would be true, but as we now understand, modern computer science has revealed the startling fact that many problems that look totally different from each other, doesn't matter if it's routing traffic, scheduling tasks, solving puzzles, tons of these problems have exactly the same computational complexity, which means the difficulty of carrying out those computational tasks is the same. In fact, these seemingly very different looking problems turn out to be just thinly disguised versions of the exact same problem.
▶︎ 4:14 And as a consequence, that means for lots of different computational tasks where we haven't figured out quick ways of solving them, it would seem it's not a failure of ingenuity on our parts, but rather it's a structural feature of computation itself. So, episode four, we're gonna
▶︎ 4:33 Do a deep dive on the most important open question in all of computer science, one of the most important open questions in really all of mathematics, something which is known as the P versus NP question. And this concerns that dichotomy of problems that we're gonna cover in the third episode, these easy problems solvable by fast algorithms, and these hard problems, problems that, as far as we can tell, appear to be unsolvable by fast algorithms.
▶︎ 5:01 And that is exactly the P versus NP question, whether or not this dichotomy is fundamental, or whether or not it might collapse, whether or not, in fact, algorithmic shortcuts, like the ones used by your map application for driving directions, whether those algorithmic shortcuts are everywhere or only very special to specific problems.
▶︎ 5:25 In the final episode, in the fifth episode, we'll begin by discussing the ramifications of the P versus NP question. We don't know the answer to that question. Maybe P is equal to NP, maybe P is different than NP. So we'll talk through what would be the implications of each of those scenarios. And then once we do that, we'll wrap up the series by pondering the question, do new computational paradigms change our understanding of what solvable or efficiently solvable means?
▶︎ 5:55 Because, for example, current technology trends you've probably heard about. There's quantum computing, there's powerful optimization solvers, like if you've ever heard of integer programming, and of course, LLMs, large language models, generative AI. All of these technologies would seem to, at least superficially, outperform the conventional expectations that we would have of computers. So the question then is, do we need to revisit all of the things that we've learned in the preceding episodes? Do these technological developments undermine traditional notions of efficient computation or do they leave those deeper limits intact? What survives when our best abstractions, the one you'll learn about in this series, are stress-tested by new technology? So that's how we'll wrap up the series.
▶︎ 6:43 Now, that's the overview. To assess whether you'd enjoy spending some time watching some of the rest of this series, let me leave you in this introductory video with a top 10 list of some of the things you can expect to learn about. And we have this nice whiteboard, so let me just take advantage of that to give you a top 10 list of highlights, or at least a sample of what we'll talk about.
▶︎ 7:21 Number 10, we're going to learn about Turing. In case you thought Alan Turing was just a code breaker, in case you only know him for the work that he did at Bletchley Park back in World War II, you'll learn that, in fact, Turing is responsible for authoring the paper which many computer scientists like myself regard as the birth of our discipline, the birth of computer science as an intellectual discipline.
▶︎ 7:54 You can come for Alan Turing, but then you should really stay for the full cast of characters, which includes many of the most famous mathematicians and computer scientists from 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, Don Knuth, all of those will appear, sometimes in big roles, sometimes with cameos, in the stories that we have to tell.
▶︎ 8:38 For the next two items on the top 10 list, we're going to learn two, I think, very surprising unexpected things about computation. First of all, if you take a task, if you take some objective you would like some computer to carry out that you'd like an algorithm for, it turns out very small changes to the nature of the task can have massive implications for how easy or difficult that computational task is. Two problems can look almost identical, and yet one can be extremely easy to solve and the other can be extremely difficult to solve.
▶︎ 9:12 On the other hand, while near-identical problems can behave very differently, very different looking problems can behave almost identically. We'll see that there's a whole range of problems that look nothing like each other, and yet all of them are really thinly disguised versions of the exact same problem. That is the nature of the theory of NP-completeness that we'll discuss.
▶︎ 9:48 You will learn why the multiplication method that you all studied in grade school is not optimal, in the sense that it will take you longer to compute the product of two numbers using what they taught all of us in grade school than if you use something called Karatsuba's method.
▶︎ 10:17 As part of the cast of characters I mentioned that appear in the story, we will. It's almost impossible to avoid, when you're talking about mathematical history, to avoid all of the peculiarities of mathematicians, both as individuals and as a community. So let's say funny mathematician stories.
▶︎ 10:49 Another thing we'll learn to talk about, as a byproduct of some of the other historical development, is computer science's fight for recognition, for respect. Once upon a time, computer science was not recognized as a serious intellectual discipline. That only started to happen in the 1960s, and then got going more in the '70s and '80s and finally by the '90s.
▶︎ 11:11 Everybody, all universities, for example, agreed that they should have a computer science department by the end of the 20th century, but that was not always an easy road. Let's say recognition of computer science as its own discipline, as its own deep discipline.
▶︎ 11:45 How do all of these ideas from the last 90 years connect to the technological developments that we're seeing today in 2026? For example, large language models, generative AI, it seems to be changing everything around us. In fact, for stuff we're going to be talking about in this series, for the nature of computation and their limits, they change nothing. Another technological development
▶︎ 12:25 You might be hearing a lot about quantum computers. People are working very, very hard right now to build bigger and bigger and more reliable quantum computers. That actually does change our notion of efficient solvability to some extent. We'll talk about that. But still, even if we succeed in building huge quantum computers, it really doesn't change the nature of computation or its limits as much as you might think.
▶︎ 13:05 And finally, number one. Number one has got to be the P versus NP question. Informally, the P versus NP question asks whether every single problem for which you can easily recognize solutions. Think about Sudoku. Someone shows you their alleged solution to a Sudoku puzzle, very easy to check whether it follows all the rules or not.
▶︎ 13:30 P versus NP asks, is it the case that for every such problem, not just Sudoku, but literally anything, where you have a you know it when you see it character of the solutions, is it the case that those problems always have algorithmic shortcuts? Is it the case that those problems with efficiently verifiable solutions always have efficient algorithms? Or alternatively, is it the case that there are problems where you can easily check solutions, like Sudoku, lots of other famous examples, if you've ever heard of the traveling salesperson problem, or TSP, that's another example. Is it the case that some such problems are fundamentally out of the reach of efficient computation, of efficient algorithms? That is the P versus NP question, which we will talk about at length.
▶︎ 14:20 So that's the list. It's a pretty awesome list actually, I think. I'm excited. I hope you're excited. If you are, I'll see you in episode one.