An Easy-Sounding Problem Yields Numbers Too Big for Our Universe
Nan Cao for Quanta Magazine
Introduction
It’s not often that 5-year-olds can grasp questions at the frontiers of computer science, but it can happen. Suppose, for instance, that a kindergartner named Alice has two apples, but she prefers oranges. Fortunately, her classmates have developed a healthy fruit-trading system with strictly enforced exchange rates: Give up an apple, say, and you can get a banana. Can Alice execute a series of trades, by picking up and offloading bananas or cantaloupes, that gets her to her favorite fruit?
It sounds simple enough. “You can go to primary school and tell [it to] children,” said Christoph Haase, a computer scientist at the University of Oxford. “People will think, ‘That must be easy.’”
But the math problem underlying Alice’s dilemma — called the reachability problem for vector addition systems — is surprisingly subtle. While some cases can be solved easily, computer scientists struggled for nearly half a century to develop a comprehensive understanding of the problem. Now, in a series of breakthroughs over the past few years, they have firmly established exactly how complex that problem can get.
It turns out that this childlike problem is absurdly, almost cartoonishly complex — so complex that practically all other famously hard computational problems look like, well, child’s play. Try to quantify the effort required to solve this problem, and soon you’ll be facing numbers so large that even counting their digits will have you reaching for numbers you’ve never heard of. Such numbers often invite comparisons to the scale of the universe, but even those analogies fall short. “That would not do it justice,” said Georg Zetzsche, a computer scientist at the Max Planck Institute for Software Systems in Kaiserslautern, Germany. “The universe is so small.”
Within Reach?
Stripped to its essence, the reachability problem is about mathematical objects called vectors, which are ordered lists of numbers. The entries in these lists are called components, and the number of components in a vector is called its dimensionality. Alice’s fruit inventory, for instance, can be described by a four-dimensional vector (a, b, c, d), whose components represent how many apples, bananas, cantaloupes and oranges she has at any given time.
A vector addition system, or VAS, is a collection of vectors representing the possible transitions between states in a system. For Alice, the transition vector (−1, −1, 1, 0) would represent the exchange of an apple and a banana for a cantaloupe. The VAS reachability problem asks whether there’s any combination of allowed transitions that can take you from a specific initial state to a specific target state — or, in mathematical terms, whether there’s any sum of transition vectors that transforms the starting vector into the target vector. There’s just one catch: No component of the vector describing the system’s state can ever drop below zero.
“That’s a very natural restriction for a model of reality,” said Wojciech Czerwiński, a computer scientist at the University of Warsaw. “You cannot have a negative number of apples.”
Merrill Sherman/Quanta Magazine
In some systems, it’s easy to determine whether the target vector is reachable. But that’s not always the case. Computer scientists are most interested in simple-looking vector addition systems in which it’s not obvious how hard it is to determine reachability. To study those cases, researchers start by defining a number that quantifies the size of a given system. This number, represented by n, encompasses the number of dimensions, the number of transitions, and other factors. They then ask how quickly the difficulty of the reachability problem can increase as n grows larger.
To answer that question, researchers use two complementary approaches. First, they search for examples of particularly tricky vector addition systems in which determining reachability requires some minimum level of effort. Those minimum levels are called “lower bounds” on the complexity of the problem — they say to researchers, “The trickiest systems for a given n are at least this hard.”
Second, researchers try to establish “upper bounds” — limits on how hard reachability can possibly get, even in the most diabolical systems. These say, “The trickiest instances for a given n are at most this hard.” To determine precisely how hard reachability is in the trickiest systems, researchers try pushing lower bounds up and upper bounds down until they meet.
The Stuff of Nightmares
Vector addition systems have a long history. Since the 1960s, computer scientists have used them to model programs that break up a computation into many small pieces and work on those pieces simultaneously. This kind of “concurrent computing” is now ubiquitous, but researchers still don’t fully understand its mathematical foundations.
In 1976, the computer scientist Richard Lipton took the first step toward understanding the complexity of the VAS reachability problem. He developed a procedure for constructing systems in which the fastest way to determine whether one state is reachable from another is to map out a sequence of transitions between them. That allowed him to use the length of the shortest path between two carefully chosen states as a measure of the difficulty of the reachability problem.
Lipton then proved he could construct a system of size n in which the shortest path between two states involved more than $latex 2^{2^n}$ transitions. That implied a corresponding double exponential lower bound on the effort required to determine reachability in his systems. It was a startling discovery — double exponential growth is the stuff of computer scientists’ nightmares. Indeed, researchers often balk even at ordinary exponential growth, which pales in comparison: $latex {2^5}= 32$, but $latex 2^{2^5}$ is over 4 billion.
Wojciech Czerwiński helped prove how difficult it is to determine whether you can get from one point to another in certain mathematical systems.
University of Warsaw
Most researchers thought Lipton had cooked up the most complex possible vector addition systems, meaning he’d raised the lower bound as high as it could go. The only thing missing, in that case, would be an upper bound to go with it — that is, a proof that there could be no system in which determining reachability was even harder. But nobody knew how to prove that. The computer scientist Ernst Mayr came closest when he proved in 1981 that it’s always possible, in principle, to determine reachability in any vector addition system. But his proof didn’t put any quantitative upper bound on how hard the problem could be. There was a floor, but no ceiling in sight.
“I certainly thought about it on and off,” Lipton said. “But after a while I gave up, and as far as I could tell no one made any progress for what was like 40 years.”
In 2015, the computer scientists Jérôme Leroux and Sylvain Schmitz finally established a quantitative upper bound — one so high that researchers assumed it was just a first step that could be pushed down to meet Lipton’s lower bound.
But that’s not what happened. In 2019, researchers discovered a lower bound far higher than Lipton’s, upending decades of conventional wisdom. The VAS reachability problem was far more complex than anyone had anticipated.
A Tower of Powers
The shocking 2019 result grew out of failure. In 2018, Czerwiński disproved a conjecture, by Leroux and Filip Mazowiecki, a computer scientist now at the University of Warsaw, that would have helped to make progress on a related problem. In subsequent discussions, the researchers hit upon a promising new way to construct extra-complex vector addition systems, which could imply a new lower bound on the VAS reachability problem, where progress had stalled for so long.
“Everything connected in my mind to VAS reachability,” Czerwiński recalled. During a semester with a light teaching load, he decided to focus exclusively on that problem, together with Leroux, Mazowiecki and two other researchers — Sławomir Lasota of the University of Warsaw and Ranko Lazić of the University of Warwick.
After a few months, their efforts paid off. Czerwiński and his colleagues demonstrated that they could construct vector addition systems in which the shortest path between two states was related to the size of the system by a mathematical operation called tetration that makes even nightmarish double exponential growth seem tame.
Tetration is a straightforward extension of a pattern connecting the most familiar operations in mathematics, beginning with addition. Add together n copies of a number, and the result is equivalent to multiplying that number by n. If you multiply together n copies of a number, that’s equivalent to exponentiation, or raising the number to the nth power. Tetration, often represented by a pair of arrows pointing up, is the next step in this sequence: Tetrating a number by n means exponentiating it n times to produce a tower of powers n stories high.
It’s hard to wrap your head around just how quickly tetration gets out of hand: $latex 2 \uparrow\uparrow 3$, or $latex 2^{2^2}$, is 16, $latex 2 \uparrow\uparrow 4$ is just over 65,000, and $latex 2 \uparrow\uparrow 5$ is a number with nearly 20,000 digits. It’s physically impossible to write down all the digits of $latex 2 \uparrow\uparrow 6$ — a liability of living in such a small universe.
In their landmark result, Czerwiński and his colleagues proved that there exist vector addition systems of size n where the best way to determine reachability is to map out a path involving more than $latex 2 \uparrow\uparrow n$ transitions, implying a new lower bound that dwarfed Lipton’s. But as head-spinning as tetration is, it still wasn’t the final word on the complexity of the problem.
To Quinquagintillion and Beyond
Just a few months after the shocking new lower bound on the complexity of VAS reachability, Leroux and Schmitz pushed down the upper bound they’d established three years earlier, but they didn’t get all the way down to tetration. Instead, they proved that the complexity of the reachability problem can’t grow faster than a mathematical monstrosity called the Ackermann function.
To understand that function, take the pattern used to define tetration to its grim conclusion. The next operation in the sequence, called pentation, represents repeated tetration; it’s followed by yet another operation (hexation) for repeated pentation, and so on.
The Ackermann function, denoted $latex A(n)$, is what you get when you move one step up this ladder of operations with each stop on the number line: $latex A(1) = 1 + 1$, $latex A(2) = 2 × 2$, $latex A(3) = 3^3$, $latex A(4)=4 \uparrow\uparrow 4=4^{4^{4^4}}$, and so on. The number of digits in $latex A(4)$ is itself a colossal number approximately equal to 1 quinquagintillion — that’s the whimsical and rarely needed name for a 1 followed by 153 zeros. “Don’t worry about Ackermann of 5,” advised Javier Esparza, a computer scientist at the Technical University of Munich.
Łukasz Orlikowski’s undergraduate research inspired a new technique used to determine the exact complexity of the VAS reachability problem.
Wojciech Czerwiński
Leroux and Schmitz’s result left a large gap between lower and upper bounds — the precise complexity of the VAS reachability problem could lie at either end of the range or anywhere in between. Czerwiński didn’t intend to let that gap stand. “We kept working on this because it was clear it’s the biggest thing we ever did in our lives,” he said.
The final breakthrough came in 2021, while Czerwiński was advising a second-year undergraduate student named Łukasz Orlikowski. He assigned Orlikowski a simple variant of the problem to get him up to speed, and Orlikowski’s work helped the two of them develop a new technique that also applied to the general reachability problem. That allowed them to raise the lower bound substantially — all the way up to Leroux and Schmitz’s Ackermann upper bound. Working independently, Leroux obtained an equivalent result around the same time.
Finally, researchers had pinned down the true complexity of the reachability problem. Czerwiński, Orlikowski and Leroux’s lower bound showed that there’s a sequence of progressively larger vector addition systems in which the shortest path between two states grows in proportion to the Ackermann function. Leroux and Schmitz’s upper bound showed that the reachability problem can’t get any more complex than that — little consolation to anyone hoping for an infallible practical procedure for solving it. It’s a striking illustration of just how subtle seemingly simple computational problems can be.
Never Finished
Researchers have continued to study the VAS reachability problem after determining its exact complexity, as many variants of the question remain unanswered. The Ackermann upper and lower bounds, for instance, don’t distinguish between the different ways of increasing n, such as increasing the dimensionality of the vectors or increasing the number of allowed transitions.
Recently, Czerwiński and his colleagues have made progress teasing apart these distinct effects by studying how quickly complexity can increase in variants of vector addition systems with fixed dimensionality. But more remains to be done — even in three dimensions, where vector addition systems are easy to visualize, the exact complexity of the reachability problem remains unknown.
“In a way, it’s just embarrassing for us,” Mazowiecki said.
Researchers hope that a better understanding of relatively simple cases will help them develop new tools to study other models of computation that are more elaborate than vector addition systems. Currently, we know almost nothing about these more elaborate models.
“I view this as part of a very fundamental quest to understand computability,” Zetzsche said.
