💻 computer science

Improving Reachability in Vector Addition Systems through Pumpability

This paper improves the reachability complexity bounds for fixed-dimensional Vector Addition Systems (VAS) by introducing a refined pumpability analysis that yields an $F_{d-2}$ upper bound and establishes PSPACE and ELEMENTARY bounds for 4-dimensional and 5-dimensional VAS, respectively, surpassing previous results inherited from Vector Addition Systems with States (VASS).

Original authors: Weijun Chen, Yuxi Fu, Yangluo Zheng

Published 2026-04-28

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Weijun Chen, Yuxi Fu, Yangluo Zheng

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are managing a massive, multi-lane highway system where cars (representing numbers) travel in specific directions. This is the world of Vector Addition Systems (VAS). In this system, you have a starting point with a certain number of cars in each lane, and a destination. The goal is to figure out: Can we get from the start to the finish without ever running out of cars in any lane? (You can't have negative cars; that's impossible).

For decades, computer scientists have known that this question can be answered (it's "decidable"), but they didn't know how hard it would be to find the answer. It turns out, for complex systems, the answer is incredibly difficult to compute—so difficult that the time required grows faster than almost any function we can imagine.

This paper, titled "Improving Reachability in Vector Addition Systems through Pumpability," by Chen, Fu, and Zheng, is like a team of traffic engineers discovering a new, smarter way to navigate these highways. They aren't just checking every possible route; they are finding shortcuts based on how the traffic "pumps" or flows.

Here is a breakdown of their discoveries using simple analogies:

1. The Problem: The "State" vs. The "Flow"

There are two versions of this highway system:

VASS (Vector Addition Systems with States): Imagine the highway has traffic lights and toll booths (states). The rules for which cars can move depend on which booth you are at. This is the more complex, popular model.
VAS (Vector Addition Systems): Imagine a highway with no traffic lights or booths. Just a flat, open road where cars move based on a fixed set of rules.

For a long time, scientists thought that if you could solve the problem for the complex version (VASS), you could solve the simple version (VAS) just as easily. But the authors realized that the simple version (VAS) is actually easier to solve than the complex one, especially when the number of lanes (dimensions) is fixed.

2. The Secret Weapon: "Pumpability"

The core of their discovery is a concept called Pumpability.

Imagine you are driving down a highway. If you can find a loop in the road where you can drive around and around, and every time you finish a lap, you end up with more cars in your lanes than when you started, you have found a pump.

Pumpable: You can keep adding cars indefinitely.
Unpumpable: You hit a wall; you can't keep adding cars without running out of space or violating the rules.

The authors refined an old technique (called "Rackoff's extraction") to look at these pumps more closely. They found that if a system is "wide" (meaning the traffic flows in many different directions), you don't need all lanes to be pumping to prove you can reach your destination. You only need most of them to be pumping.

The Analogy:
Think of a 5-lane highway. Old methods said, "To prove you can get through, you need to show you can pump cars in all 5 lanes."
The authors say, "Actually, if you can pump cars in just 4 of the lanes, that's enough to prove you can get through!"
Because you only need to check 4 lanes instead of 5, the math becomes significantly simpler and faster.

3. The Results: Faster Answers for Specific Highways

By using this "4-out-of-5" pumping trick, the authors achieved two major breakthroughs:

A. The General Rule (The "Fd-2" Improvement)

For a highway with $d$ lanes, the old method said the answer could take a massive amount of time (a complexity level called $F_d$ ).
The authors proved that for the simple highway (VAS), the time required is actually much lower ( $F_{d-2}$ ).

Simple Translation: If the old method said, "It might take a billion years to solve," the new method says, "It might only take a million years." It's still a long time, but it's a huge improvement in the math world.

B. The Low-Dimensional Wins (The 4 and 5 Lane Highways)

The authors looked specifically at highways with 4 and 5 lanes, which are common in real-world simulations.

5-Lane Highways (5-VAS): Previously, no one knew if there was a "manageable" limit to how long it would take to solve this. The authors proved that for 5 lanes, the answer is definitely within a "manageable" (Elementary) range. It's no longer in the realm of the impossible.
4-Lane Highways (4-VAS): They proved that for 4 lanes, the problem is solvable in PSPACE.
- What does this mean? Imagine you have a computer with a limited amount of memory (like a backpack). The old methods might have required a backpack the size of a planet. The new method shows you can solve this 4-lane problem with a backpack that fits in a standard room.

4. The "Projection" Trick

To solve the 4-lane problem, they invented a new way to "project" or flatten the highway.
Imagine you have a 3D sculpture (the complex traffic flow). Instead of trying to analyze the whole 3D shape, they found a way to shine a light on it to create a 2D shadow that keeps all the essential information.
They showed that a complex 2-dimensional "geometric" system can be converted into a simple 2-lane highway system. This allowed them to use existing, fast tools to solve problems that previously seemed too big.

Summary

This paper is about efficiency.

The Old Way: "Check every possible path, and assume the worst-case scenario for every single lane."
The New Way: "Look for the 'pumps' (loops that add cars). If most lanes are pumping, you can ignore the rest and solve the problem much faster."

By realizing that the simple highway system (VAS) has fewer constraints than the complex one (VASS), the authors have shaved off significant layers of complexity, making it possible to solve reachability problems for 4 and 5 lanes much more efficiently than ever before. They haven't built a new car; they've just found a much better map.

1. Problem Statement

The paper addresses the reachability problem in Vector Addition Systems (VAS), a fundamental model of concurrency equivalent to Petri nets. The problem asks whether a target configuration (a vector of non-negative integers) is reachable from a source configuration via a sequence of allowed integer vector additions (transitions).

Context: While the general reachability problem for VAS is known to be Ackermann-complete (extremely high complexity), researchers focus on fixed-dimensional VAS ( $d$ -VAS) to understand the complexity landscape.
The Gap: For $d$ -dimensional VAS with States (VASS), the best known upper bound is $F_d$ (the $d$ -th level of the fast-growing hierarchy). Since VAS can be simulated by VASS with a constant number of extra dimensions, this $F_d$ bound was inherited by VAS. However, it was unclear if VAS (which lacks the finite state control of VASS) could have tighter bounds.
Specific Challenge: In low dimensions, the gap is significant. For example, reachability in 2-VASS is PSPACE-complete, but for 5-VAS, no elementary upper bound was previously known.

2. Methodology

The authors develop a refined analysis based on pumpability and geometric dimension, improving upon Rackoff's classical extraction technique.

A. Refined Pumpability Analysis

Standard Rackoff Extraction: Traditionally, if a run in a $d$ -dimensional system is "unbounded" (all coordinates exceed a threshold), one can construct a run where all coordinates are large. If a configuration is not pumpable, at least one coordinate remains bounded, allowing for dimension reduction.
The Paper's Innovation: The authors prove that for wide sequential VAS (where the cone of cycle effects equals the span of cycle effects), if $d-1$ coordinates are large, the system is guaranteed to be pumpable.
Consequence: In the "unpumpable" case, this implies two coordinates must remain bounded simultaneously. This allows for a reduction of the dimension by 2 rather than 1 in specific scenarios.

B. Geometric Dimension and Projection

Geometric Dimension: Defined as the dimension of the vector space spanned by the effects of simple cycles ( $\dim_{cyc}$ ).
Projection Techniques: The paper introduces a "sign-reflecting projection" technique. For geometrically 2-dimensional systems, the authors show how to project the system onto 2 coordinates while preserving reachability properties.
- They handle projective cycle spaces (where a projection exists directly) and non-projective spaces (by encoding bounded coordinates into states to reduce dimension).
- This allows converting complex geometrically 2-dimensional VASS into standard 2-VASS with polynomial size overhead.

C. Fine-Grained Run Characterization

The authors characterize the shortest runs in $d$ -VAS not just by a single lower-dimensional VASS, but by:

A $(d-2)$ -VASS, OR
A sequence of two VASSes with geometric dimension at most $d-3$ .
This dichotomy allows leveraging known tight bounds for lower dimensions (e.g., 2-VASS and 3-VASS) to bound higher-dimensional VAS.

3. Key Contributions and Results

A. General Dimension Improvement ( $d \ge 5$ )

Theorem: Reachability in $(d+2)$ -VAS is in $F_d$ for every $d \ge 3$ .
Significance: This improves the inherited $F_{d+2}$ bound from VASS to $F_d$ . It demonstrates that VAS is strictly easier than VASS in fixed dimensions.
Mechanism: By reducing the $(d+2)$ -VAS problem to a VASS with component-dimension at most $d$ , the authors apply the known $F_d$ bound for VASS.

B. Low-Dimensional Breakthroughs

The paper establishes the first elementary upper bounds for dimensions greater than 3:

5-VAS: Reachability is in ELEMENTARY.
- Reasoning: Shortest runs are bounded by 3-VASS (which has an elementary bound) or sequences of geometrically 2-dimensional VASSes (which can be converted to linear path schemes with exponential bounds).
4-VAS: Reachability is in PSPACE (binary encoding) and NL-complete (unary encoding).
- Reasoning: Shortest runs are bounded by 2-VASS or geometrically 2-dimensional VASSes. The authors provide a novel reduction converting geometrically 2-dimensional VASSes to 2-VASSes with polynomial size, allowing the application of existing 2-VASS PSPACE bounds.

C. Geometrically 2-Dimensional VASS Complexity

The paper resolves the complexity of reachability for geometrically 2-dimensional VASSes:
- Binary Encoding: PSPACE-complete.
- Unary Encoding (Fixed $d$ ): NL-complete.
- Unary Encoding (Unfixed $d$ ): NP-complete.
This clarifies the complexity landscape for a class of systems that had previously only been known to be in PSPACE.

4. Significance

Bridging the VAS/VASS Gap: The paper proves that the lack of finite state control in VAS allows for significantly better complexity bounds than VASS in fixed dimensions, resolving a long-standing open question about whether $F_d$ bounds for VASS were tight for VAS.
Elementary Bounds for High Dimensions: It provides the first elementary upper bounds for 5-VAS, moving beyond the Ackermann-level complexity of the general case and the non-elementary bounds of previous VASS-based approaches.
New Technical Tools: The introduction of sign-reflecting projections and the refined pumpability analysis (extracting two bounded coordinates) provides powerful new tools for analyzing vector addition systems and Petri nets.
Practical Implications: By establishing PSPACE and NL bounds for 4-VAS and geometrically 2-dimensional systems, the paper suggests that verification tools for these specific classes of concurrent systems could be much more efficient than previously thought.

Summary of Complexity Improvements

System	Previous Best Upper Bound	New Upper Bound (This Paper)
$(d+2)$ -VAS	$F_{d+2}$ (inherited from VASS)	$F_d$
5-VAS	Unknown (Non-elementary implied)	ELEMENTARY
4-VAS	Unknown (Non-elementary implied)	PSPACE (Binary) / NL (Unary)
Geo-2-VASS	PSPACE	PSPACE / NP / NL (Refined)

In conclusion, this paper fundamentally advances the understanding of Vector Addition Systems by leveraging geometric properties and refined pumpability arguments to decouple the complexity of VAS from that of VASS, yielding significantly tighter complexity bounds for fixed-dimensional systems.