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 uparrowuparrow 3$, or $latex 2^{2^2}$, is 16, $latex 2 ­uparrowuparrow ­ 4$ is just over 65,000, and $latex 2 ­uparrowuparrow ­5$ is a number with nearly 20,000 digits. It’s physically impossible to write down all the digits of $latex 2 uparrowuparrow ­­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 uparrowuparrow ­­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 uparrowuparrow 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.