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