Today, I want to continue talking about computation. Computation is a concept that transcends any particular technology; it is really part of the mysteries of the universe. In the first episode, our main focus was establishing the limitations of computation: the idea that there are things computers will fundamentally never be able to do, such as solve the halting problem. Today, I want to take a different emphasis and talk about the positive applications of computation. Computers can't do everything, but we all know from day-to-day life that they help us do an enormous amount of useful work, and that is what I want to focus on.
The key concept I want to introduce is the algorithm. An algorithm is essentially a recipe for how to systematically achieve some goal or solve some problem. In episode one, when we discussed Turing machines having sets of rules, that set of rules was basically encoding an algorithm, a recipe for going about systematically solving a problem. From the recipes you are already familiar with, you know there may be a sequence of steps to perform in order, there may be loops in which a sequence of steps is repeated over and over, and there may be conditionals, or if-then-else branches. If the hamburger patties are frozen, you follow one set of instructions; if they are not, you follow another. If you have done any coding at all, you will recognize that these constructs map quite directly into the loops and if-then-else statements you would write in code.
The recipes you follow in a kitchen, viewed as algorithms, are honestly not very interesting. It turns out, however, that algorithms for very natural problems can sometimes be mind-bogglingly clever, exploiting unexpected shortcuts, and this has proved to be the case over and over again throughout the history of computer science. Through two examples today, one about arithmetic and one about networks, I want to give you a taste of the creativity of algorithms and of algorithm designers.
While my main goal is to appreciate the genius we have seen in algorithm design over the years, there is something lurking in the background as well. If you think back to establishing limitations on what computers can do, the fact that algorithms can be so clever, and even downright inscrutable, while simultaneously being useful, is exactly why it is so difficult to prove limitations on computation. This will become especially clear when we discuss the P versus NP problem later, and it is yet another reason to admire Turing's achievement: he was showing limitations on something that is, in fact, extraordinarily powerful. With that, let us turn to the two examples.
We will begin with an example in arithmetic, and then move to a second example concerning networks. The starting point is about as basic as it gets: given two numbers, multiply them. We all learned how to do this at some point in grade school, and it seemed like that was the end of the story. What I want to tell you about today is a different approach, Karatsuba's method for multiplying integers, which, believe it or not, is a fundamentally more efficient, fundamentally faster method than the one you learned as a child.
To set the stage for Karatsuba's multiplication algorithm, we need to go back to the year 1960. Zooming out slightly, the mid-twentieth century was a golden era for algorithm design. Computers were suddenly becoming available and were being used in an increasing number of high-value applications, yet historically very few people had thought carefully about algorithms. There were many gems waiting to be found, particularly in the 1950s and 1960s.
Picture Moscow State University in 1960, and a research seminar run by the celebrated mathematician Andrei Kolmogorov. By that point, mechanical computers were being used for a wide range of calculations, and Kolmogorov was among the first mathematicians to become genuinely obsessed with the question of how best to carry out computations by machine. Could one be more clever and complete a calculation in five minutes instead of ten? Or, conversely, was some familiar method of computation, say, the way we all learned to multiply in fourth grade, already optimal, the best possible approach?
That was Kolmogorov's focus in the late 1950s and early 1960s. At his weekly seminar, he asserted, indeed conjectured, that integer multiplication as taught in school was essentially the best one could do. The partial-products method we all learned as children, he believed, simply needed a mathematical proof of its optimality; nothing more clever was possible.
There was one student in that seminar, Anatoly Karatsuba, who brought exactly the attitude one needs to design algorithms professionally. Algorithm designers are people who are very hard to please, never content, always asking whether a given solution could be improved. Karatsuba applied that disposition directly to Kolmogorov's conjecture: granted, one could simply follow the traditional method, but could one do better? Working against the prevailing intuition that nothing could surpass what we learned in third or fourth grade, Karatsuba did find a fundamentally better method, which I will describe in a moment.
In 1995, Karatsuba wrote an article that included a retrospective of those early-1960s years with Kolmogorov. He was twenty-three years old at the time. Kolmogorov ran a weekly seminar, and one week (let's say a Monday) Kolmogorov put forward his conjecture that there could be no better method for multiplying numbers than the one we all learned in grade school. The following Monday, Karatsuba arrived with a solution. In a single week, he had disproved the conjecture.
Karatsuba reports that Kolmogorov was very agitated, because the result contradicted what had seemed a thoroughly plausible conjecture. At the next meeting of the seminar, Kolmogorov himself presented Karatsuba's method to the participants, and at that point, the seminar was terminated. It had lost its purpose once Karatsuba demonstrated that a genuinely better multiplication algorithm existed.
At this point, you are probably wondering exactly how Karatsuba's method works. If you are like most people, your first reaction is: what else could you possibly do besides what we learned as children? To answer that, it helps to first recall precisely what we did learn. Let's multiply 5,678 by 1,234 as a concrete example.
The grade-school procedure works by computing partial products. You multiply 4 times the top number, then shift and multiply 3 times the top, then shift again and multiply 2 times the top, and finally shift once more and multiply 1 times the top. Carrying out those steps gives four partial products: 22,712; 17,034; 11,356; and 5,678. Adding them all up yields 7,006,652.
That is what we mean by multiplying two numbers, and that is the algorithm we all learned in grade school. We probably never thought of it as an algorithm; it was just a sequence of steps we followed to reach a result. But that is precisely what it is. Notice that multiplying two four-digit numbers fills in a table of roughly four rows and four columns of single-digit operations, and then sums the results.
The pattern scales directly. If you multiply two numbers that each have 100 digits, you produce 100 partial products, each containing roughly 100 individual entries, all of which must then be added together. The work grows as the square of the number of digits. The question Kolmogorov believed was settled, and Karatsuba proved was not, is whether any fundamentally more efficient approach exists.
There are two ideas in Karatsuba's method. The first idea will initially seem bizarre; you might wonder why anyone would ever do it that way. The second idea is what unlocks the power of the first, so bear with me. The first idea will be familiar to those of you who have studied programming, but if you haven't, you may not have encountered it before. It is the idea of recursion: solving a problem by first reducing it to one or more smaller instances of the same problem.
There are real-life examples of recursion. Imagine you are trying to organize a tennis tournament: you have a collection of players and you want to arrange matches to produce a champion. If you have only one player, the problem is trivial; they are the champion. If you have two players, they play a match and the winner is the champion. But what if you are running a Grand Slam tournament with 128 players? How should you arrange things to eventually arrive at a champion?
One approach is to solve the problem recursively. You take your 128 players, pair them up into 64 first-round matches, play those matches, and you are left with 64 winners. You then recursively run a tennis tournament on those 64 winners. That is the essence of recursion: faced with a large problem you cannot solve all at once, you reduce it to one or more smaller versions of the same problem and make progress from there. Recursion is a fundamental tool in algorithm design and programming more broadly.
At this point you might be wondering what recursion has to do with multiplying two numbers. In the tennis example, it is clear how playing first-round matches reduces 128 players to 64. But if you are asked to multiply two given numbers, what does it even mean to do that recursively? It would have to mean multiplying smaller numbers against each other, but these are the numbers we were given.
In fact, there is a natural recursive approach to integer multiplication. The key is to split each number into its first half and its second half. If we are given two four-digit numbers, we can think of each one as a pair of two-digit numbers, and then ask whether we can reduce the multiplication of two four-digit numbers to a series of multiplications involving only two-digit numbers. That is the recursive strategy for integer multiplication we will now develop.
This idea alone is not going to be the full story. We will need a second idea, which I will get to in a moment. First, let us think about how we can treat these four-digit numbers as pairs of two-digit numbers.
Take 5,678. We can write that number as 5,600 plus 78, that is, the first two digits scaled appropriately, plus the last two digits. Similarly, we write the second number as 1,200 plus 34. The product of those two expressions is identical to the product of the original two numbers; it is literally the same two numbers written in expanded form.
Now we expand. Multiplying out the two binomials gives four terms: 56 times 12, times 10,000; then 56 times 34, times 100; then 78 times 12, times 100; and finally 78 times 34. The result of this computation is exactly the same as the product of the original two four-digit numbers, and nothing has changed mathematically.
At this point the role of recursion becomes visible. To evaluate this expanded expression, there are really only four non-trivial multiplications to perform. Multiplying by 10,000 or by 100 is trivial: you simply append zeros. The genuine work lies in the four products circled in green, each of which involves only two-digit numbers. We had a problem of multiplying two four-digit numbers, and we have reduced it to four multiplications of two-digit numbers. The numbers are smaller, even though there are more of them. That reduction to smaller instances of the same problem is the hallmark of recursion.
I should be honest, though: our progress so far is quite modest. All we have really done is reorganize the same calculations that the grade-school algorithm would perform, just in a different order. This recursive algorithm, as described so far, is no faster than the standard approach. That brings us to the second key idea.
The second key idea is identifying redundant work and reusing computation rather than redoing it. Using this principle of reuse, we will actually be able to save one of the four multiplications. We can reduce the multiplication of two four-digit numbers to three pairs of two-digit multiplications, not four. It is not obvious how to do this, and that was Karatsuba's great second insight, which is what we will explore next.
To see where the redundancy lies, take the expression we arrived at previously and group its terms. Two of the four terms are multiplied by 100, so we collect those together. The first term, involving 10,000, and the fourth term remain unchanged. The second and third terms, 56 × 34 and 78 × 12, are grouped and multiplied by 100. This regrouping changes nothing about the value of the expression; it is purely a rearrangement.
Here is the key insight. To evaluate this expression, we do not actually care about the product of 56 and 34 individually, nor do we care about the product of 78 and 12 individually. All we need is their sum. If someone handed us the value of 56 × 34 + 78 × 12, that is sufficient: we append two zeros and add the remaining terms. Up to this point, we had been assuming, without justification, that the only way to evaluate the expression was to compute each of those two products separately. That assumption is unnecessary.
This is the central idea in Karatsuba's algorithm: if we can compute the sum of two products without computing each product individually, we save a multiplication. The natural question is how. What could we possibly do other than compute the two products separately?
This is where the clever exploitation of reuse enters. We know we must compute 56 × 12 and 78 × 34 regardless. Karatsuba's question is whether we can piggyback on those two unavoidable multiplications to obtain the quantity we need, the sum 56 × 34 + 78 × 12, using only one additional multiplication. And in fact, we can. The trick requires some experimentation: knowing that two of the products are already in hand, one searches for a way to recover the remaining quantity without computing its two components separately. After enough trial and error, a eureka moment arrives, which we will see next.
Suppose we performed the following calculation. Take 56 plus 78, the sum of the digits of the first number, and multiply it by 12 plus 34. That gives us 134 times 46. Now let's expand the product. We get 56 times 12, which is a quantity we already knew we had to compute, and 78 times 34, which is also something we already knew we had to compute. But we also get the cross terms: 78 times 12, plus 56 times 34, which is exactly what we were looking for.
With a single multiplication, 134 times 46, we have computed a number that contains the term we care about, plus two distractions: 56 times 12 and 78 times 34. Crucially, those distractions are quantities whose values we already know, because we have to compute them anyway. If we subtract them out, we are left with precisely the cross terms we wanted in the first place.
You may have gotten a little lost along the way, so let me recap by organizing these calculations in a more direct fashion. Nothing new will be introduced, only a cleaner presentation of what we have already established.
Here is the alternative way to compute the product of 5,678 and 1,234. In step one, we compute the product 56 times 12, which comes from the first of the four terms when we expand the two expressions. In step two, we compute the product of the second pair: 78 times 34. Step three is the tricky part: we compute the product 134 times 46. Remember where these numbers come from. 134 is 78 plus 56, and 46 is 34 plus 12. This product therefore contains the cross term 78 times 12 plus 56 times 34, along with the two additional terms from steps one and two, so we subtract those out.
To be explicit about the numbers: 56 times 12 gives 672, 78 times 34 gives 2,652, and 134 times 46 gives 6,164. After subtracting out the results of the first two multiplications, we are left with 2,840. Now we simply add up the three results, taking care to append the correct number of trailing zeros to each.
The first product, 672, corresponds to the 5,600 and 1,200 components, so we append four zeros. The second product, 2,652, corresponds to the 78 and 34 components, so it requires no zeros. The cross term, 2,840, requires two zeros appended. Carrying out this final addition, 6,720,000 plus 2,652 plus 284,000, yields 7,006,652. That is Karatsuba's method for integer multiplication.
We have only verified that this works with one specific example, but the intuition should be very strong that there is nothing special about the numbers five, six, seven, eight, and one, two, three, four. You can use this exact same recipe, this exact same algorithm, to multiply any pair of numbers you want. And this really is fundamentally faster, fundamentally more efficient, than the algorithm we learned in grade school.
That is not totally obvious, and I will not prove it in detail here, but the intuition is this: by virtue of reuse, by observing that in the expansion there are really only three quantities we care about, we can compute those three quantities with only three multiplications rather than four. That reduction is exactly the source of the extra efficiency, and exactly why this improves over what we learned in grade school.
This is not merely an academic algorithm; it really is faster in practice. For those of you who know the programming language Python, the standard Python libraries, when asked to multiply large numbers of 70 digits or more, will in fact use Karatsuba's method rather than the grade-school method we all learned many years ago.
If I had to summarize the genius of Karatsuba's method in one sentence, I would say this: it turns out there is redundant work hidden inside the grade-school algorithm, and Karatsuba's insight was to structure the computation so that the redundancy becomes visible and can be eliminated, reusing information across three multiplications rather than four.
The main takeaways here are a couple. First, appreciate that remarkable algorithmic shortcuts exist, perhaps not for every problem, but certainly for some, where algorithms turn out to be far more effective than you might have guessed. Always remember the flip side as well: when thinking about the limits of computation, examples like Karatsuba's method make it genuinely terrifying to try to prove that no algorithm can do better, which should make us all the more appreciative of Turing's work establishing limits such as the undecidability of the halting problem.
Something closely related to Karatsuba's method, which I will leave as extra credit, is Strassen's algorithm for matrix multiplication. Matrix multiplication is a supremely important practical problem. Modern machine learning algorithms spend the bulk of their cycles performing matrix multiplications, so a significant fraction of the computation happening right now, in 2026, involves multiplying matrices.
There is a straightforward method for multiplying matrices, which is what you learn when you first encounter them, and it involves eight multiplications. If you thought Karatsuba's trick of reducing four multiplications to three was remarkable, you have to look into Strassen's trick for reducing eight multiplications to seven. When it comes to the intimidation of trying to prove limitations on algorithms, given how clever algorithms can be, I know of no better example of where that intimidation comes from than Strassen's algorithm for matrix multiplication.
Our second example algorithm concerns a problem in networks, a very familiar one. You need to get from point A to point B, and you ask your favorite map application for driving directions, hopefully finding the fastest route available. These days we all take that technology for granted, but underpinning it are clever algorithms that exploit powerful algorithmic shortcuts. This second part of the episode is meant to give you a feel for the nature of those shortcuts.
To organize how we think about the problem, to organize the options and the routes, let's think about a network. Consider the example network drawn here on the whiteboard. Each arrow, which in this context is often called an edge, represents a road from one point to another. The circles, sometimes called vertices, represent intersections where different roads meet. The origin is A, and the destination is B.
Let's use a simple model of travel times. Each edge is annotated with a number representing the travel time along that road in minutes. In this example, the travel times are three minutes, four minutes, one minute, five minutes, and two minutes, respectively. These are one-way streets, so you can only travel in the direction of the arrow.
Given this setup, how do you get from A to B as quickly as possible? This particular instance is not hard to solve by inspection. There are exactly three routes from A to B that respect the one-way constraints. The northern route takes three plus four, or seven minutes. The southern route takes five plus two, also seven minutes, so the two are tied. Then there is the zigzag path, which has more hops and longer driving directions, but a travel time of only three plus one plus two, or six minutes. The zigzag path is therefore the quickest route from A to B.
The method we just used to determine the shortest path, examining every possible route, is known as exhaustive search.
When you have a collection of options, such as routes from A to B, and you want to find the best one, the one with the smallest travel time, one straightforward approach is to go through the options one by one and remember the best. That is exactly what we just did. There were only three paths from A to B; we checked them all, found that the zigzag route was the fastest, and confidently proclaimed it the shortest route. This approach is called exhaustive search: examine every option, remember the best one.
When there are only a handful of options, exhaustive search is simple enough to perform by hand or by inspection. You could do it manually for dozens of options, perhaps even hundreds. Modern computers can scan through billions of options without difficulty, so you might conclude that exhaustive search is essentially all we ever need, that for any problem arising in everyday life, such as finding the best driving route to a relative's house in another state, we can simply let the computer look at all the options and return the best one. But can we be certain that everyday problems have only billions of options? Could there be far, far more than that?
To see what is at stake, consider a second network. It is a simple network, and the best route from A to B will be easy to identify, but it reveals a fundamental limitation of exhaustive search. To travel from A to B, you make four consecutive binary decisions: at each step, you take either the northern road or the southern road, and each time you arrive back at the same type of junction. With the travel times shown, the answer is obvious: take north, then south, then north, then south again, for a total travel time of 16 minutes. Any deviation from that red path would merely substitute a slower road for a faster one.
Notice, however, that when you reasoned through this problem, you did not use exhaustive search. You exploited an algorithmic shortcut. The number of distinct paths from A to B is two choices for the first hop, multiplied by two for the second, multiplied by two for the third, multiplied by two for the fourth, that is, two raised to the fourth power, or 16 separate options. Yet you never considered all 16. Instead, you mentally pruned every path that used a slower road, immediately discarding anything that passed through the roads labeled 2, 4, 6, or 8, and arrived directly at the optimal red path labeled 1, 3, 5, 7.
A natural response is: so what? Even if exhaustive search is slightly wasteful here, a computer blazes through 16 options in an instant. The concern, however, is what happens when the network grows. Imagine replicating those binary decision points many more times along a much longer network. In the four-decision network, the number of options was two to the fourth, or 16. Each time we add another binary decision, that count doubles, and it does not take many doublings before the number of options grows far beyond what any computer can handle.
Imagine you had 10 binary decisions to make in a row. Think about driving from New York City to Cape Cod, where there are potentially a large number of decision points along the route. With 10 such decisions, you would not have 24 possibilities but 210, which is 1,024. You know you are talking to a computer scientist when they have all the powers of two automatically memorized. Among friends, let us call 1,024 roughly 1,000. That would be tedious for a human to enumerate, but entirely manageable: a computer could certainly handle it.
What if there were 20 decisions? Two to the twentieth power is approximately one million. Thirty decisions gives us roughly a billion. Forty decisions gives us roughly a trillion. A trillion starts to become significant even for computers: not impossible, but you begin to feel the strain.
Now imagine driving from the West Coast to the East Coast, say, from Burlington to La Jolla, and suppose there are at least 265 different decisions to make along the way. Exponential growth is a wild thing, and it defies human intuition. We are often first taught this lesson through the power of compounding interest, and this is another vivid illustration of the same phenomenon. A network with 265 binary choices is not hard to write down; it would fit on a whiteboard or a table without difficulty. Yet the number of distinct routes through that network, the number of options exhaustive search would have to check, is, without exaggeration, approximately the estimated number of atoms in the known universe. Two to the 265th power is the standard estimate for that count.
Exhaustive search would still qualify as an algorithm in the sense of Turing: it is a well-defined recipe that, if carried out to completion, would correctly identify the shortest path. But it is one that defies the physical limitations of our universe, one that would not complete in our lifetime or in anyone else's, not just given today's technology, but given technology a thousand years from now.
The takeaway is this. Exhaustive search looks perfectly reasonable when you are solving very small problems. But for problems of even medium size, the kind we routinely submit to a map application, the number of options exhaustive search must consider is completely infeasible. The shortest path problem, while not undecidable in the sense of Turing, would be for all practical purposes unsolvable if we were confined to exhaustive search and could not unlock any algorithmic shortcuts.
Given that exhaustive search would be completely infeasible once the network in question is even medium-sized, the obvious question is: how does a phone provide driving directions even for destinations on the other side of the country? Thinking it through logically, it clearly cannot be doing exhaustive search; it must be doing something more clever than that. And indeed, in the example network on the right, there is already an algorithmic shortcut visible. Each of the four routing decisions can be treated independently: take the shorter road at the first step, the shorter road at the second step, and so on. There is no need to examine all sixteen options.
That example is, of course, a very special network. The deeper question is whether, for general, messy road networks that look nothing like that tidy example, there exists some algorithmic shortcut that a program could exploit to compute driving directions efficiently. Happily, the answer is yes. There are shortest-path algorithms, the kind driving your map application, that take advantage of exactly those ideas. One famous starting point is Dijkstra's algorithm, a celebrated algorithm for computing shortest paths dating from the mid-1950s. Several other researchers arrived at similar algorithms at roughly the same time, but the method is conventionally named after Edsger Dijkstra.
The key idea behind Dijkstra's algorithm is the clever reuse of work. When enumerating all sixteen paths and assessing each independently, a great deal of computation is redundant: different paths generally share edges, and there is no reason to reassess those shared edges repeatedly. The shortcut is to make a decision about a given edge once and for all, and never revisit it. Work is performed once and reused, rather than duplicated.
At a high level, Dijkstra's algorithm can be visualized as blowing up a balloon around the origin, exploring in all directions simultaneously. After one minute of travel time, the algorithm determines how far it can reach along every outgoing road. After two minutes, it expands further. After three minutes, it reaches the end of one road and sixty percent of the way down another. At four minutes, it discovers a way to reach a particular intersection by combining two edges, and so on. The balloon inflates outward, step by step, in all directions at once.
When the balloon has expanded far enough, it reaches the destination, and the shortest path from the origin to that destination is revealed at that moment. Crucially, nothing is ever reconsidered: the algorithm only radiates outward, never revisiting territory it has already covered. What may not be immediately obvious from this description is how to organize this balloon-expansion process as an efficient computer program. A course in algorithms would show that the entire computation can indeed be organized in a highly efficient, very fast manner. Dijkstra's algorithm is the foundation on which modern shortest-path methods are built, even though state-of-the-art driving directions layer additional ideas on top of it.
Today we covered Karatsuba's method for multiplying integers and shortest-path algorithms such as Dijkstra's algorithm. The takeaway I want you to have is less narrowly about these two problems themselves and more broadly about appreciating, first, that algorithms are fantastically useful for problems we want to solve every single day, and second, that computers and the algorithms that run on them can be even more powerful than you might expect. At least for many problems, including the two we examined today, there are shortcuts, not easily seen, but identified by very clever algorithm designers and put to work in state-of-the-art algorithms.
More generally, I am honestly a little jealous of the people working in algorithms in the 1940s, 1950s, and 1960s, when computers were first being built and their value was first being appreciated. There was so much exciting work to do. There is still a tremendous amount of exciting work to do in algorithms and computer science more broadly, do not misunderstand me, but it was greatest hit after greatest hit, year after year through the fifties and sixties. It seemed like an extraordinary time to be in the field.
One of the highlights of that early era, for example, would be the simplex method.
The simplex method for linear programming was discovered by George Dantzig. Even if you think you haven't heard of George Dantzig, you probably have, perhaps through the inspirational story about the power of positive thinking. It sounds apocryphal, but here is how it goes: a student walks into class five minutes late, sees math problems written on the blackboard, and assumes they must be homework. He missed what the professor said, so he simply copies down the problems and resolves to turn in his solutions later.
The student works on the problems and finds them surprisingly difficult. Three weeks later, he finally goes to the professor's office and, finding no one there, slips his solutions under the door. That midnight, there is a frantic knocking on his dorm room door. It is the professor, holding the student's work and saying, "These weren't homework problems. These are the two biggest open questions in this area of statistics." The moral being: if you don't know something is supposed to be too hard, it may actually help you do it.
You probably assumed this story was apocryphal. It is not; it is literally about George Dantzig. His doctoral thesis from the Berkeley statistics department consists of solutions to exactly those two problems, and that was in 1939. Fast forward to the mid-to-late 1940s: Dantzig is working for the military in the aftermath of World War II, and a superior challenges him to find a systematic method for military planning, figuring out how much supplies to send to different locations.
Dantzig's response was to discover both the abstraction of a linear program, which is enormously useful in its own right, and a remarkable algorithm for solving linear programs in practice with great efficiency: the simplex method. This is one of the genuine gems of the field. Eighty years later, the simplex method is still used constantly and remains an extraordinarily powerful algorithm, a landmark result from the late 1940s.
Here is one more Dantzig story, since it ties into another character who has appeared in these lectures. We mentioned John von Neumann briefly in the first episode, one of the most celebrated mathematicians of the 20th century and a central figure in the early computing efforts behind the EDVAC and the ENIAC. Dantzig writes in his memoirs about meeting von Neumann, perhaps for the first time, perhaps for the only time, around 1947 or 1948.
Dantzig was young and nervous. Von Neumann was already enormously famous, and Dantzig was partly trying to verify that the simplex method was genuinely new, that no one else had already discovered it. He began the meeting with a motivating example, something along the lines of imagining that you want to ship supplies from one location to another. Von Neumann, who was legendary for processing ideas at what seemed like a hundred times the speed of any other mathematician, immediately interrupted him: "Get to the point. You're wasting my time. What do you want to know?"
Dantzig, somewhat offended, replied that if von Neumann wanted the fast version, he could have it. He went to the whiteboard and covered linear programming and the simplex method in roughly five minutes. Von Neumann listened, and it became clear that the simplex method was indeed new to him. By all accounts, Dantzig had genuinely discovered it first. However, von Neumann immediately recognized that the concept of linear programming was deeply connected to the game theory he had been working on, and in particular to his famous minimax theorem, which concerns how, in a zero-sum game, the order of play between the two players does not matter in a certain precise sense.
Right there in the room, von Neumann absorbed Dantzig's formulation of linear programming and realized in real time that his minimax theorem corresponded to what we now call the theory of linear programming duality, something Dantzig himself had not yet recognized. Von Neumann explained that for each linear program there is a corresponding dual linear program, and that this relationship gives rise to remarkable properties such as strong duality and complementary slackness. The first papers on LP duality were subsequently co-authored by Dantzig and von Neumann.
This is the kind of exchange that was happening in that era. To have been a fly on the wall at any of these meetings would have been extraordinary. At least we have the firsthand accounts left behind by the people who were there.
The 1940s, '50s, and '60s were a golden era for algorithms. More and more computational problems fell to the genius ideas of those early algorithm designers: the simplex method, Dijkstra's algorithm, and many other examples. If you tried to extrapolate from that trajectory, you might conclude that eventually we would have clever algorithms for all possible problems, that we could solve anything we wanted.
But before any of that era, there was Turing's 1936 paper. From the very moment we began thinking seriously about algorithms, we knew they had limitations. We knew there would be natural problems, like the halting problem, that would never be solved by any mechanical procedure, never solved by any computer, no matter how good the technology. So we see this back-and-forth between what computation can do and what it cannot.
At this point, you might concede: "Fine. The halting problem. I get it. It would be useful to have an algorithm for it, but we're never going to have one." But consider the problems of day-to-day life: driving directions, organizing a daily schedule, accommodating conflicts with other people. Surely these simple, natural problems should all be easily solved by a computer. It's only more technical, esoteric problems like the halting problem that elude computation, everything else should be easy, right?
But don't forget the astronomical number of options we encountered even in the shortest path problem. If you need to make 265 independent decisions, the number of different options to consider exceeds the estimated number of atoms in the known universe. Exhaustive search is completely infeasible at that scale. For the shortest path problem, this wasn't a serious obstacle, because we found an algorithmic shortcut. That is precisely what Dijkstra's algorithm exploits, reusing work across all the different possible options.
The real question, then, is whether algorithmic shortcuts always exist for the natural problems that arise in everyday life, or whether some of those problems genuinely have nothing better to offer than an exhaustive search through all possible outcomes. George Dantzig had exactly this experience. Problem after problem fell to the simplex method; there were algorithms for maximum flow and many other challenges, an impressive string of successes. Yet there was one problem Dantzig spent enormous effort on, called the traveling salesperson problem, or TSP, that resisted every idea he and his colleagues could devise.
Could it be that problems like the traveling salesperson problem, which we will examine more closely next time, have both an astronomical number of options and no fundamentally superior method for sifting through them other than exhaustive search? That question leads us to one of the deepest open problems in all of mathematics, and certainly the deepest open question in computer science: P versus NP, which will be the subject of the next two episodes.