Numbers Too Big for Our Universe

Gödel’s Lost Letter and P=NP 2023-12-17

Starting from games and models that look like child’s play

Ben Brubaker is a staff writer covering computer science for Quanta. He previously covered physics as a freelance journalist, and his writing has also appeared in Scientific American, Physics Today, and elsewhere. He has a Ph.D. in physics from Yale University in 2007.

Brubaker wrote an article last week on the vector addition system (VAS) reachability problem. A VAS is just a finite set ${V}$ of integer vectors of some dimension ${d}$ . The vectors can have negative entries but the starting vector ${s}$ must be non-negative. At any point, you have a current vector ${u}$ . The transition rule is:

You can step from ${u}$ to ${u+v}$ if ${v \in V}$ and the vector ${u+v}$ is non-negative.

The non-negative stipulation makes the order of adding vectors matter so as to frustrate simple analyses of ${V}$ . In 1975–1976, I constructed cases where the shortest path from ${s}$ to a given goal vector ${t}$ is doubly exponential in ${d}$ and the size of ${V}$ . Furthermore, I showed that any exponential-space computation could translate into this kind of example. In consequence I showed that there is no way to decide whether ${t}$ is reachable from ${s}$ via ${V}$ in less than exponential space. This goes for any decision procedure—not just ones that try tracing all possible legal paths.

This left open whether exponential space—or allowing doubly exponential time irrespective of space—is sufficient. That question was recently resolved in a way nobody I knew expected.

His Quanta Article

Here is what Brubaker writes about my paper:

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 ${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, because double exponential growth is the stuff of computer scientists’ nightmares. Indeed, researchers often balk even at ordinary exponential growth, which pales in comparison: ${2^5 = 32}$ , but ${2^{2^5}}$ is already over 4 billion.

I didn’t quite prove the double-exponential time lower bound in full generality, just for certain programming systems. It still could be that any exponential space computation can be done in singly exponential time—this would follow if ${\mathsf{PSPACE = P}}$ , for instance. But what didn’t happen was anyone showing a matching upper bound. Not close. Brubaker continues:

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 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.

TL;DR: what turns out to be the ceiling is not something we’d call in sight. And it’s not clear what insight it gives. It’s far more terrible on the “nightmare” scale than what Brubaker says about doubly-exponential.

Far From Child’s Play

The article leads with a nice graphic of what an exponential “tower” looks like:

By Nan Cao for Quanta

The lede explains the apple and the orange:

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.”

The trades don’t allow the kids to “owe” commodities at any point. That’s the non-negativity requirement. But there is also a requirement of “waste-not, want-not”: you have to get the target vector ${t}$ exactly.

To vary the article’s example, if there’s a rule where Alice can get a free apple plus a pear anytime, she has to take both. Suppose she can later trade three apples and a pear for one orange. We have the start vector ${s = (0,0,0)}$ and ${V}$ composed of ${u = (1,1,0)}$ and ${v = (-3,-1,1)}$ . Alice can form ${u+u+u+v}$ to get ${(0,2,1)}$ and collect her orange. But she still has two pears. She cannot reach ${(0,0,1)}$ by this trading scheme.

Trading Models

Ken points out a different model that was known to Mayr and Albert Meyer and goes back to Marvin Minsky. This is a machine that has no tapes but only a fixed number of counters. It can increment a counter, and also decrement it if its value is positive; it can test the counter for zero so as to avoid even trying to make its value negative.

Minsky showed that these simple machines can do any exponential space computation with only four counters. Then he showed they can do it with only two counters—let’s call them ${x}$ and ${y}$ . A typical instruction in Minsky’s machine might be:

if in state ${q}$ , you can decrement ${x}$ , increment ${y}$ , and go to state ${r}$ .

If we take ${d = 2 + |Q|}$ , where ${Q}$ is the state set of a given Minsky machine ${M}$ , then we can make a VAS that simulates rules like this. Say the counters are the first two coordinates, the machine’s start state is next, and states ${q}$ and ${r}$ and then an accepting state ${f}$ are at the end. Then the instruction corresponds to the vector

$\displaystyle (-1,+1,\dots,-1,+1,0)$

If the counters have values ${3}$ and ${6}$ before the instruction is executed, then the current vector is ${(3,6,\dots,1,0,0)}$ . The instruction changes it to ${(2,7,\dots,0,1,0)}$ . The last ${|Q|}$ -many dimensions only have values ${0}$ or ${1}$ . The start vector could be ${s = (0,0,1,\dots,0)}$ with the counters zeroed, or could give initial values to ${x}$ and/or ${y}$ . The goal vector—after the machine without loss of generality zeroes its counters before accepting—is ${t = (0,0,\dots,0,0,1)}$ .

What Mayr and Meyer imagined instead was that ${x}$ and ${y}$ and the state labels were variables used in a polynomial ideal. The above instruction then becomes the basic polynomial

$\displaystyle \alpha = ry - xq.$

The above current state is just the monomial ${m = qx^3 y^6}$ . In a polynomial ideal you can add any multiple of a polynomial in your basic set. So you can add ${x^2 y^6}$ times ${\alpha}$ . Then the next state is ${m + x^2 y^6\alpha = qx^3 y^6 + rx^2 y^7 - qx^3y^6}$ , which simplifies to just ${rx^2 y^7}$ . The powers are not allowed to go negative. The upshot is that the monomial ${s}$ can become ${t}$ if and only if ${M}$ accepts.

What Mayr and Meyer thus proved is that whether ${s}$ can reach ${t}$ —or whether the simple polynomial ${t - s}$ belongs to the ideal generated by the instruction polynomials—is hard for exponential space. They also proved that the general problem of whether a given polynomial belongs to a given ideal is in exponential space, thus complete for it. This was their famous 1982 paper giving tight bounds for the polynomial ideal membership problem.

The VAS lower bound could have been proved that way—but attention was on the upper-bound side. Surely richer cases of polynomial ideals could capture the requirements of a VAS? Mayr could not show this—he found only decision procedures of astronomical complexity. Perhaps some higher algebraic notion than a polynomial ideal could do it more accessibly? I must say that I (Ken writing this section) have been greatly interested in Mayr-Meyer—for reasons touched on in the “minimal monomials” section of this old post—but never thought to apply it to VAS. Well, the attempt at trading the underlying model would have been fruitless anyway.

Ack!

The truth—as expounded in the rest of Brubaker’s article—is that exponential space is not an upper bound. Nor doubly-exponential time, nor any stack of exponentials. As has come out only recently, the VAS reachability problem requires time and space that grow as Ackermann’s function.

Brubaker illustrates the simplest form of Ackermann’s function: ${A(1) = 1+1 = 2}$ , ${A(2) = 2\cdot 2 = 4}$ , ${A(3) = 3^3 = 27}$ , and

$\displaystyle A(4) = 4^{4^{4^4}} = ?$

The number ${A(4)}$ is too long to write down, and as for the next number:

“Don’t worry about Ackermann of 5.”

That is quoting Javier Esparza, a computer scientist at the Technical University of Munich. This is where Mayr has been since 1993.

So the numbers involved in deciding even relatively small cases of VAS grow out of all proportion. This is not even what we mean by galactic algorithm—the concrete numbers are too big.

Open Problems

Ken and I hope you enjoy Brubaker’s fun article on the VAS problem. I was quite excited to see him cover this result of mine last week. I always enjoyed working on the problem—even though it was so many years ago. Hope you do too.