Easy-Sounding Problems That Aren't Easy

Back when we were all locked down with little to do, I spent some time revisiting my love the weird corners of math. Quanta Magazine brings us a story of really big numbers. An Easy-Sounding Problem Yields Numbers Too Big for Our Universe

Let's go with the easy sounding problem.

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

Sounds easy. It isn't easy.

When you convert that to a form that mathematicians can prove things about, it becomes known as a vector reachability problem in a vector addition system (VAS). In 1976 Richard Lipton took the first steps to put bounds on the problem.

Lipton then proved he could construct a system of size n in which the shortest path between two states involved more than 2²ⁿ 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: 2⁵=32, but 2²⁵ is over 4 billion.

And that is only the beginning. Skip ahead to the present day...

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.

There is an explanation of tetration, the next step up the ladder from exponentiation, at the link above. It is short, and confusing, but complete. I like my long-winded explanation which you can find at this link from 2020.

It’s hard to wrap your head around just how quickly tetration gets out of hand: 2↑↑3, or 2²², is 16, 2↑↑4 is just over 65,000, and 2↑↑5 is a number with nearly 20,000 digits. It’s physically impossible to write down all the digits of 2↑↑6 — a liability of living in such a small universe.

The rest of the article is interesting, and they get to use numbers like quinquagintillion (a 1 with 153 zeros after it).