The blank spots

In the qubit lab we ran into a question that no textbook answers: is there anything a quantum computer can do quickly that an ordinary one can’t? Questions like that have turned up in the course before. This is the last chapter, so we’ll draw a map of what nobody knows. But first, back to where we started: the course opened with the number $2^{1000}$ and five surprises. Here are the number and four of the five surprises again, in a single program; the third one, the tree, is drawn by a turtle and won’t fit on a line.

In Chapter 0 each of these lines was a surprise; now they are exercises. The 302-digit number is a Python integer, which has as many digits as it needs (Chapter 28), and 302 is $\lfloor 1000 \lg 2 \rfloor + 1$. Twenty questions for a million are the binary search of Chapter 20 plus a logarithm: $2^{20} > 10^6$. The race is twelve and a half million comparisons against sixty-five thousand, a square against $n \log n$, and no processor will close that gap (Chapter 13). The quine is a template with a hole and the repr of Chapter 7; with the same self-reference, in Chapter 56, we proved that no Oracle can exist.

The fifth surprise, though, is a surprise still. The number 27 takes 111 steps, every number up to $2^{71}$ ends up at one, and nobody knows why: not us after sixty-five chapters, and not the best mathematicians in the world. The course began with a blank spot: in computer science, the edge of the map is in sight from the first page.

The map of the unknown

Old mapmakers left unexplored lands blank, which was more honest than drawing sea serpents on them. Below is such a map for computer science, drawn on top of this course. The introduction is in the middle, the eleven parts are around it, and the dots are chapters. The ones you have read in this browser are filled in. Past the shore the fog begins, and in it lie the questions the course led you up to and stopped at. The lines show which chapters a question can be seen from.

The three kinds of marks are not equal. A rock is a proven limit: there we know that the road goes no further, and that knowledge is as solid as a working algorithm. The halting problem, the $n \log n$ lower bound for comparison sorting, the impossibility of agreement when a server may stay silent for as long as it likes: these are the cliffs of the coast. They were found by proofs, and no new processor will move them. A flag is a spot that has been closed. A blank spot is a place where nobody knows even whether there is a cliff or a passage.

It is curious where the spots fell. They are thickest around the algorithms and Parts IX–XI, while off the coasts of the machine, the operating system and the networks the fog is nearly empty. Not everything is known there, of course, but engineering questions (how much further transistors can shrink, how to build something reliable out of unreliable parts) are seldom posed so that the answer is a theorem. The spots on this map are all of one sort: precise questions that a proof or an algorithm will one day answer.

The coastline moves, and faster than you might think. While this course was being written, several flags went up on the map. In July 2024 the bbchallenge community announced that it had proved $BB(5) = 47\,176\,870$ (Chapter 56). In 2025 Ran Duan and his coauthors showed that Dijkstra’s wave from Chapter 24 is not the best possible way to find shortest paths in a directed graph: their algorithm takes $O(m \log^{2/3} n)$ steps and gets around the “sorting barrier” that the heap imposes on Dijkstra. And one spot was closed by a student who didn’t know it was a spot.

The edge of knowledge runs closer than a textbook makes it look. A textbook tells of closed questions because those can be told as a coherent story, while the open ones lie right past the last paragraph of almost every chapter. Here are the main spots on the map, biggest first.

The biggest spot

You know it from Chapter 57. Checking a coloring, a timetable or a filled-in sudoku is easy; finding one seems to be hard, and nobody has managed to prove that “seems” since 1971, when Stephen Cook posed the question in its present form. As of October 3, 2026, nobody has collected the Clay Mathematics Institute’s million dollars. In William Gasarch’s latest poll, 88 percent of experts said they believe $\mathrm P \ne \mathrm{NP}$, but a vote is not a proof.

The question is about all algorithms at once, including those nobody has thought of yet. To prove that a problem is hard means ruling out in advance a Karatsuba whom Kolmogorov didn’t foresee (Chapter 21), the Strassen we’ll meet shortly, and everyone who comes after them. Worse, there are known barriers: whole families of techniques that are proved not to help here. The diagonal argument that defeated the Oracle in Chapter 56 doesn’t work, as Baker, Gill and Solovay showed in 1975. In the 1990s Alexander Razborov and Steven Rudich described “natural proofs,” the way almost every lower bound for logic circuits known at the time was built, and proved that if sufficiently strong one-way functions exist, then no natural proof can establish $\mathrm P \ne \mathrm{NP}$. That makes a loop: cryptographers hope that one-way functions exist, and their existence closes the most familiar road to a proof of $\mathrm P \ne \mathrm{NP}$, without which they can’t exist.

Do one-way functions exist?

In Chapter 60 we admitted that all of public-key cryptography stands on an untested foundation. A one-way function is easy to compute and hard to invert, and hard for almost every input. If such functions exist, then $\mathrm P \ne \mathrm{NP}$: inverting a function means finding an input from an output, and checking what you found is easy. The converse is unknown. It may turn out that $\mathrm P \ne \mathrm{NP}$ and yet hard cases are rare, so that a random key is almost always easy. Then there would be no ciphers, even though the main question was settled “the right way.”

In 1995 Russell Impagliazzo described five possible worlds. In Algorithmica $\mathrm P = \mathrm{NP}$, and there is no cryptography. In Heuristica hard problems exist, but on average everything is solved quickly. In Pessiland there are problems that are hard on average, but no secret can be hidden in them. In Minicrypt one-way functions exist, which is enough for signatures and passwords but not for public keys. In Cryptomania there is everything we did in Part X. We behave as if we lived in Cryptomania, but nobody knows which of the five is ours.

In 2020 Yanyi Liu and Rafael Pass found a link to Chapter 47. Remember Kolmogorov complexity, the length of the shortest program that prints a given string? Give that program a time limit and you get a measure of compressibility that can, at least in principle, be computed. Liu and Pass proved that one-way functions exist if and only if this measure is hard to compute on average. The cryptographers’ spot and the compressors’ spot turned out to be the same spot.

A spot within a spot: identical graphs

If $\mathrm P \ne \mathrm{NP}$, there must be problems between the easy ones and the NP-complete ones; that is Ladner’s theorem from Chapter 57. There are few candidates for the middle ground: factoring, the discrete logarithm and graph isomorphism. You are given two graphs. Can the vertices of the first be renamed so that it becomes the second? The certificate is the renaming itself, and checking it is easy: you’ll do it in the task below. Finding one is harder. Trying every renaming means $n!$ options, which is hopeless even for the graphs of Chapter 19.

In November 2015 László Babai of the University of Chicago announced an algorithm that solves the problem in quasi-polynomial time, $2^{O((\log n)^c)}$: slower than any polynomial, but incomparably faster than an exponential. Harald Helfgott found an error in the analysis, and on January 4, 2017, Babai withdrew the bound. Five days later he announced a fix, and Helfgott, having gone through it, confirmed that it was correct and showed that one can take $c = 3$. How big is the gain? Place your bet before you calculate.

The table is sobering. On a thousand vertices the quasi-polynomial is still level with a full search. It overtakes the previous record, $2^{O(\sqrt{n \log n})}$, set by Babai and Eugene Luks in 1983, only at around six million vertices, and even that only if you forget the constant factors. In practice it computes nothing faster: graphs are compared by programs that since the 1970s have worked well on random graphs, though in the worst case they take exponential time. What it changes is the map. If graph isomorphism were NP-complete, Babai’s algorithm would solve every problem in NP in quasi-polynomial time, and almost nobody believes that. So isomorphism most likely lies in the middle ground, in a country whose very existence depends on the biggest spot.

A spot that shrinks

Most spots on the map have sat still for decades. This one is a rare exception: its edge can be plotted on a chart, and it creeps.

Seven instead of eight looks like a trifle until you remember Chapter 21. An $n \times n$ matrix is cut into four blocks, and Strassen’s formulas work for blocks as they do for numbers. That gives the recurrence $T(n) = 7\,T(n/2) + O(n^2)$, and by the master theorem the time grows as $n^{\log_2 7} \approx n^{2.807}$. The cell below checks the formulas on a thousand random pairs and counts the gain.

For $8192 \times 8192$ matrices the difference is already more than fivefold. A thousand matches are evidence, but not yet a proof. In the task below you’ll see that for formulas of this kind, sixteen well-chosen checks already are a proof.

Strassen started a race, as Karatsuba had before him. The number $\omega$ such that $n \times n$ matrices can be multiplied in $O(n^{\omega + \varepsilon})$ operations for every $\varepsilon > 0$, while no exponent below $\omega$ will do, is called the matrix multiplication exponent. The schoolbook rule gives $\omega \le 3$, Strassen $\omega < 2.81$. From below, only $\omega \ge 2$ can be seen: the answer has $n^2$ numbers, and each of them has to be written down, if nothing else. Everything in between is a blank spot, and for half a century its right edge has been pushed to the left.

The steepest part of the chart is the 1970s and early 1980s: Pan, Bini and his coauthors, Schönhage, Coppersmith and Winograd knocked off almost a third of a unit. In 1990 Coppersmith and Winograd reached $2.3755$, and for twenty years the chart stood still. Since 2010 the bound has been moving again, but in the third to sixth decimal place: Andrew Stothers, Virginia Vassilevska Williams, François Le Gall and others keep refining one and the same “laser method.” Extend the trend through different years and the question “when do we get to two?” gets very different answers. A line through 1969–1990 promised two before 2010; a line through the last fifteen years promises it thousands of years from now. A straight line knows only the pace of past records, and a new method can change that pace either way.

The records of recent decades aren’t used in practice. Their constant factors are so large that the gain would show up only on matrices that wouldn’t fit in any memory. Such algorithms are jokingly called galactic algorithms: they win on inputs of astronomical size. The libraries that multiply matrices for neural networks use the schoolbook rule, only done with great care for the cache of Chapter 34 and in parallel, and they bring in Strassen-style schemes now and then. But every such record moves the edge of the spot.

In recent years machines have joined the search. In 2022 DeepMind’s AlphaTensor system found a scheme for $4 \times 4$ matrices with 47 multiplications instead of the 49 of Strassen applied twice, though only for arithmetic modulo 2. And on August 17, 2026, a preprint by ten authors appeared: seven researchers at Google DeepMind and three authors of earlier records, Josh Alman, Virginia Vassilevska Williams and Renfei Zhou. They attacked the optimization problem inside the laser method with new tools, among them AlphaEvolve, an agent that writes and improves programs with the help of a language model. The new bound is $\omega < 2.371177$; the previous one was $2.371339$. As of October 3, 2026, it is a preprint on arXiv, with no record of publication in a journal or at a conference. The bound will be accepted once people or programs have checked it; that an AI helped find it settles nothing either way.

$\omega$ has a younger sibling from Chapter 21: multiplying numbers. There the race that Karatsuba began reached $O(n \log n)$ in 2019, thanks to David Harvey and Joris van der Hoeven; their paper appeared in the Annals of Mathematics in 2021. Schönhage and Strassen, who set the record of 1971, had guessed that nothing better than $n \log n$ is possible. The upper bound has now reached that guess, but no matching lower bound has been proved, and the gap, one logarithm wide, remains open.

Gaps

The spot around $\omega$ has two shores. The right one is the upper bound: $\omega < 2.371177$, because here is an algorithm. The left one is the lower bound: $\omega \ge 2$, because here is a proof that no algorithm can be faster. To move the right shore, it is enough to invent one method. To move the left one, you need an argument about all methods at once, including those not yet invented. That is why upper bounds move while lower bounds stand still for decades, and most often they are the trivial “you have to at least read the input.”

Below are the gaps for several problems from the course. The gray part of each scale is what is provably impossible, the colored part is what we know how to do, and the white between them is the spot. Tap a row to see how its right shore moved.

The only row with no white in it is comparison sorting. In Chapter 20 we proved with a decision tree that any sort that only compares makes at least $\log_2 n! \approx n \log_2 n$ comparisons, and merge sort makes about that many. That is a rare piece of luck: a problem about which everything is known. The other rows are the norm. For the traveling salesman with the triangle inequality from Chapter 58, the best known fast algorithm gives a tour at most $1.5 - 10^{-34}$ times longer than the optimum (on average over its own random choices), while all that has been proved is that no guarantee better than $123/122 \approx 1.008$ is possible if $\mathrm P \ne \mathrm{NP}$. Between them lies almost half an optimum’s worth of ignorance. For shortest paths the right shore moved in 2025, and the left one still stands at $m$, the number of edges: every edge has to be looked at.

The edge beyond which nothing shows

There are spots of another kind. With P and NP it is at least clear what an answer would look like: an algorithm or a proof. With some questions nobody knows whether they can be answered at all.

Take the beavers first. After the victory over five states in 2024 (Chapter 56), the bbchallenge participants took on six. The best six-state champion known was found by the participant mxdys in June 2025: it halts, but its number of steps exceeds $2 \uparrow\uparrow\uparrow 5$, a tower of twos whose height is itself a tower of twos 65,536 high. That is a lower bound on $BB(6)$. No upper bound at all is known, and by Radó’s theorem no computable function bounds $BB(n)$ from above for every $n$. To find $BB(6)$, one has to settle, for every six-state machine, whether it halts. At the end of September 2026, 815 machines remained unsettled, counting equivalent ones (those that differ only in the names of their states, for example) as a single machine. Among them is Antihydra from the same chapter: it halts only if a Collatz-like sequence behaves in a way nobody expects it to. The project’s participants state the conclusion plainly: finding $BB(6)$ will mean solving a Collatz-like problem.

The Collatz conjecture itself is open as of October 3, 2026. Computers have checked every number up to $2^{71}$; that is a 2025 result of David Bařina. The strongest statement proved so far is Terence Tao’s from 2019: almost every number has a path that sinks arbitrarily low, below any function of the starting number that grows to infinity, however slowly. “Almost every” has a precise meaning here, in terms of density, and exceptions are not ruled out. To get a feel for what $2^{71}$ means, we’ll check as many numbers on the server as we can in one second. There is a handy shortcut: if every number below $n$ has already been checked, it is enough to make sure that the path of $n$ drops below $n$, since from there it follows ground already covered.

Our server checks millions of numbers a second and would still spend tens of millions of years on the way to $2^{71}$. The record rests on parallel computing, on programs written in languages closer to the hardware of Part IV, and on shortcuts that throw out most numbers without computing anything. None of it brings a proof one step closer: however many numbers you check, a counterexample may lie further on.

There are reasons to suspect that some spots of this kind can’t be closed at all. In 1972 John Conway proved that for generalized Collatz-like rules the question “will it reach one?” is undecidable (Chapter 56). And there is a machine with 745 states that halts if and only if ZFC, the system of axioms on which nearly all of mathematics rests, is inconsistent. So if ZFC is consistent, the exact value of $BB(745)$ can’t be established by its means: Gödel’s theorem from Königsberg dressed up as a beaver. Somewhere between six states and 745 runs a border beyond which “blank spot” means “this cannot be known.” Where it runs is unknown too.

On the horizon

The last three spots lie at the edge of Part XI. They are the ones closest to the news, so they call for an especially sober look.

Qubits. You saw this spot up close a moment ago, in Chapter 64, so we’ll keep it brief. Nobody knows whether BQP is larger than P, and a proof would also separate P from PSPACE (Chapter 57), a spot of the same caliber as the main one. Nobody knows how BQP relates to NP. And from the other side, nobody knows whether a fast way of factoring numbers without any qubits will turn up: then RSA would fall before a large quantum computer is built, and Shor’s algorithm would lose its main trump card. The spot cuts both ways. Any new experiment with qubits may prove to be a breakthrough, or a problem that ordinary computers haven’t yet learned to solve quickly, as already happened with the 2019 experiment (Chapter 64, “How to read the news”).

Chess. Checkers was solved in 2007, with a draw, and Connect Four in 1988, with a win for the first player (Chapter 62). How a perfect game of chess ends is unknown. In the summer of 2012 Vladimir Makhnychev and Victor Zakharov used the Lomonosov supercomputer at Moscow State University to work out almost every position with seven pieces, about 140 terabytes of tables, and by 2018 the seven-piece positions had been worked out completely. Positions with eight pieces, as of 2026, have been worked out only in part. The starting position has thirty-two.

Machines that learn. To the eleventh big question Chapter 63 answered “yes, but”: a network finds a rule that no programmer wrote, and it goes wrong where something new doesn’t resemble what it has seen. What lies behind that “but” is the most crowded spot on the map. There is no accepted theory of why huge networks, able to learn their training set by heart, still generalize to new data (the exam in Chapter 63). Nobody knows where the abilities of language models, which predict the next word, run out, or which parts of their behavior deserve to be called reasoning. And these machines are already at work on the edge of our map: the 2026 bound on $\omega$ from the section above was obtained with the help of an agent built around a language model. But the agent’s role is to propose, and what accepts a proposal is a proof, checked by a person or a program. In the Sprout course you can take such a model apart with your own hands: there you train a language model from scratch.

The toolbox

Now for the map of the known. You can see the blank spots because you have reached their edge, and you didn’t get there empty-handed. Over 65 chapters you have written a Lisp interpreter, a compiler for a machine you built yourself out of gates, a search engine for this site’s textbooks, a SAT solver, a key exchange and a bot for Connect Four. If you solved the tasks in this browser, everything you wrote in them is below.

The course has more than two hundred forty tasks, but far fewer ideas beneath them, and the ideas keep coming back. Split in half: the twenty questions of Chapter 0, binary search, merge sort, Karatsuba, Strassen, the B-tree in a database, hunting down the commit with the bug in git. Remember instead of recomputing: dynamic programming, the processor cache, a database index. Do the work in advance: the hash of a key, the search engine’s inverted index, the navigator’s landmarks. Hide complexity under a layer: the function, the process, the protocol, virtual memory. Reduce one problem to another: coloring to a formula, halting to printing “hello,” any problem in NP to SAT. Flip a coin: Monte Carlo, the salt in a hash table, Miller–Rabin, game-tree search. Keep an invariant: the bounds of binary search, the Paxos quorum, the correctness of a greedy step. Look at yourself: the quine, the contrarian, the compiler that compiles itself. The next time a problem won’t give way, run through this list; the way in is most likely on it.

And the eleven questions of Chapter 0 have all been answered. A program can print itself (Chapter 7). What makes one program faster than another is its growth function (13). A navigation app runs Dijkstra’s wave over a graph, with a heap (24). A computer is assembled from switches (32). A hundred programs share two cores thanks to the OS kernel, the scheduler and locks (39). Billions of machines work with nobody in charge because no layer of the network rests on a single machine, and replicas agree by majority (44). A search engine does its searching in advance (48). One program understands another through a tree (52). Problems that no computer will solve do exist (56). A secret is agreed on through a one-way function (60). A machine learns what it wasn’t taught, within the bounds of its data (63). The map of the unknown casts a shadow over two of these answers. The tenth rests on one-way functions, whose existence is unproved, and the eleventh on generalization, which nobody has properly explained.

The last task: a guide

The last task of the course is a small project where several ideas meet. You’ll build a guide to this very course: a person types what they want to understand (“hash table”, “blank spots”, even a misspelled “turing machne”), and the program finds the chapter and lays out a route, which chapters to read and in what order. You already have the data: it is the course graph from Chapter 19.

The file holds every title twice, in Russian and in English. The guide stitches together skills from different parts of the course. Understanding a query takes the strings and normalization of Chapter 7 and Chapter 48. Forgiving a typo takes the Damerau distance of Chapter 22. Collecting all the chapters needed takes a graph traversal without recursion, because a chain of dependencies can be longer than the stack (Chapter 9). Putting them in order takes the topological sort of Chapter 19 with a heap from Chapter 18. Not nodding off on a large course takes the complexity estimates of Chapter 13. Turning a request down clearly, on a cycle or an unknown word, takes the exceptions of Chapter 11. If you solved the tasks “Reading order” and “Damerau’s amendment,” your functions are in the toolbox above; help yourself.

What next

This chapter has no next one. Sixty-five chapters ago the course promised to go down from a line of Python to the switches and climb back up, and at the end to ask what no computer can ever do. All of that is behind you, and instead of the wall a chapter usually ends with, this one ends at a fork in the road.

If you want to go deeper into what you have covered, the next courses are being prepared on the computer science portal: a catalog of algorithms with visualizations and code, a course on systems and networks that goes further than this one, and computer graphics from the pixel to ray tracing. While they are in the works, every task of this course is collected on the practice page, and every term in the glossary. If you want to understand the mathematics the course stood on (graphs, probability, remainders, linear algebra), there is “Mathematics, the Queen of the Sciences,” and its last chapter, “The frontier,” is the same kind of map of the unknown, only drawn by mathematicians: it has the same Collatz and P versus NP, and next to them the Millennium Prize Problems. If you want to look inside the machines that learn, in the Sprout course you’ll train your own language model from scratch and talk to it in your browser.

Geniuses aren’t the only ones who close blank spots. $BB(5)$ was settled by amateurs and professionals who gathered around a single website; Yao’s conjecture was overturned by a student who didn’t know what he was overturning; and the bbchallenge project is open to everyone and is working through the six-state machines right now. To join in, what you already have is enough: you can write a program, estimate its running time, check someone else’s claim and refuse to believe a pretty extrapolation.

The course began with the words “Code first.” We’ll finish with code too. The program below takes a random number around $10^{30}$, hundreds of millions of times larger than $2^{71}$, and leads it along the Collatz rule. Whatever number you get has almost certainly never been checked by anyone, ever.

It got there. One more point at the edge of the map, and once again nothing is proved. This is where the course ends.