💬 NLP

Reachability in 3-VAS

This paper establishes that the reachability problem for symmetric vector addition systems in dimension 3 is PSPACE-hard, thereby settling the exact complexity of reachability for 3-VAS and 4-VAS as PSPACE-complete.

Original authors: Łukasz Kamiński, Sławomir Lasota

Published 2026-08-06

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Łukasz Kamiński, Sławomir Lasota

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 a world built entirely of invisible counters, like a giant, cosmic game of "add and subtract" where you can never go below zero. This is the realm of Vector Addition Systems (VAS), a mathematical model used by computer scientists to understand how complex systems—like traffic lights, computer networks, or even the flow of data in a cloud—move from one state to another. In this world, you start with a certain number of tokens in different piles, and you have a set of rules that let you move tokens around. The big question is: Can you ever reach a specific target arrangement?

For decades, computer scientists have been trying to figure out exactly how hard this question is to answer. If the system is simple, it's easy. If it's huge and chaotic, it might be impossible to solve in a lifetime. But there's a tricky middle ground: systems with a fixed, small number of counters (dimensions). For systems with three or four counters, we've been stuck in a fog. We know the answer isn't too easy (it's harder than basic math puzzles), but we didn't know if it was a nightmare that would take a supercomputer a million years to solve, or just a tough puzzle that a smart human could crack with enough time. This paper steps into that fog and shines a light, proving that for these specific 3-counter and 4-counter systems, the problem is indeed a "hard" puzzle, but one that is solvable within a reasonable timeframe for a powerful computer.

The Puzzle of the Three-Counter Machine

The authors of this paper, Łukasz Kamiński and Sławomir Lasota, tackled a specific version of this puzzle involving Vector Addition Systems in dimension 3 (3-VAS). Think of a 3-VAS as a machine with three dials, each holding a number. You have a set of "moves" that add or subtract numbers from these dials, but you can never let a dial drop below zero. The goal is to see if you can get from a starting set of numbers to a specific target set.

For a long time, the complexity of this problem for 3-dial machines was a mystery. It was known to be somewhere between "NP" (a class of problems that are hard but solvable) and "PSPACE" (a class of problems that are very hard and require a lot of memory to solve). The authors wanted to know: Is it just hard, or is it very hard?

To solve this, they didn't just look at the general 3-dial machine. They looked at a special, more organized version called a symmetric 3-VAS. In a symmetric system, the rules are perfectly balanced. If you have a rule that says "add 2 to dial A and subtract 1 from dial B," the system also automatically has rules that do the same thing for any other combination of dials. It's like a game where the rules don't care which specific dial is which; they only care about the pattern of the move.

The Big Discovery: It's a "PSPACE" Problem

The paper's main finding is a definitive proof: The reachability problem for symmetric 3-VAS is PSPACE-hard.

In plain English, this means that figuring out if you can reach a target in these systems is as difficult as the hardest problems that a computer can solve using a reasonable amount of memory. It's not just "hard"; it belongs to the elite club of "very hard" problems.

Here is how they proved it:

The Setup: They started with a known hard problem (a bounded version of a 1-dial machine) and showed how to translate it into a 3-dial symmetric machine.
The Trick: They used a clever encoding scheme. Imagine the 1-dial machine's counter value is stored across the three dials of the new machine in a very specific way. They used huge numbers and specific patterns to ensure that the 3-dial machine could only make moves that perfectly mimicked the 1-dial machine.
The "Deadlock" Check: The authors designed the rules so that if the 3-dial machine tried to make a move that didn't correspond to the original problem, it would immediately get stuck (reach a "deadlock") and fail. This forced the 3-dial machine to follow the exact path of the harder problem.
The Result: Since the original problem was known to be very hard, and the 3-dial machine had to solve it to succeed, the 3-dial problem must also be very hard.

What This Means for the Rest of the World

Because the symmetric version is a subset of the general version (if the special, balanced version is hard, the messy, general version must be at least that hard), the authors' result settles the score for the general case too.

By combining their new proof with previous work that showed these problems aren't impossible (they have an upper limit of PSPACE), the authors conclude that the reachability problem for both symmetric and general 3-VAS (and 4-VAS) is PSPACE-complete.

This is a big deal because it closes the book on the complexity of these specific dimensions. We now know exactly where they sit on the scale of difficulty: they are tough, memory-intensive puzzles, but they are solvable.

The One Mystery Left Behind

The paper also points out a remaining gap in our knowledge. While they solved the puzzle for 3 and 4 dials, the complexity for 2-dial systems (2-VAS) remains a mystery. It is still stuck between "easy" (NP) and "very hard" (PSPACE). The authors suggest that the techniques they used to crack the 3-dial code don't easily translate to the 2-dial world, leaving that specific door still locked.

In summary, this paper acts like a master key, unlocking the complexity class for 3 and 4-dimensional vector addition systems. It confirms that while these systems are complex and require significant computing power to analyze, they are firmly within the realm of what computers can theoretically solve, bringing us one step closer to fully understanding the limits of automated verification in concurrent systems.

Technical Summary: Reachability in 3-VAS⋆

Problem Statement
The paper addresses the exact computational complexity of the reachability problem for Vector Addition Systems (VAS) in fixed low dimensions. While the general reachability problem for VAS (equivalent to Petri nets) was recently settled as Ackermannian-complete, the complexity for fixed dimensions remains a critical open area. Specifically, for dimensions 2, 3, and 4, the reachability problem for stateless VAS was previously known to be sandwiched between NP and PSPACE. The authors focus on resolving the complexity for dimension 3 (3-VAS) and its symmetric fragment.

Methodology
The authors employ a series of reductions to establish hardness results, building upon existing lower bounds for symmetric Vector Addition Systems with States (VASS).

Reduction from Bounded 1-VASS:
The proof begins by establishing the PSPACE-hardness of the reachability problem for source-bounded symmetric 3-VASS. This is achieved by reducing from the PSPACE-complete reachability problem for bounded 1-VASS.
- Simulation Strategy: The reduction simulates a 1-VASS counter $m$ (bounded by $B$ ) using two counters in a 3-VASS configuration $(m, m, 2B-m)$ .
- Symmetry Handling: To enforce symmetry, the transition set is expanded to include all permutations of coordinates. The construction ensures that only specific transitions (and their symmetric counterparts) are executable without violating non-negativity constraints, effectively forcing the system to follow the intended simulation path.
Reduction from Symmetric 3-VASS to Symmetric 3-VAS:
The core contribution is a reduction from the reachability problem in source-bounded symmetric 3-VASS to symmetric 3-VAS (stateless).
- Control State Elimination: Inspired by classical control-state elimination, the authors transform the stateful system into a stateless one. They introduce dummy control states to ensure that valid runs have lengths divisible by 3, with non-zero effects occurring only at specific steps.
- Scale Separation: The reduction maps a configuration $p(u)$ of the VASS to a configuration $v_p + u$ in the VAS, where $v_p$ is a vector dependent on the control state $p$ . The components of $v_p$ are constructed with distinct orders of magnitude (e.g., $B \cdot A_p$ , $B \cdot p$ , $0$) to distinguish coordinates and control states.
- Vector Construction: For every transition $(p, w, q)$ in the VASS, the VAS includes transitions derived from the vector $v_{pq} = \ell(v_q) - v_p$ and its permutations. The proof demonstrates that due to the magnitude differences and the source-boundedness of the original system, only the "correct" permutation of the transition vector can be fired without causing a counter to drop below zero. This forces the stateless VAS to simulate the stateful VASS step-by-step.

Key Contributions and Results

Theorem 1: The reachability problem for symmetric 3-VAS is PSPACE-hard.
Corollary 2: By combining Theorem 1 with previously established PSPACE upper bounds (specifically from [2] for 4-VAS and [9] for symmetric VASS), the authors conclude that the reachability problem is PSPACE-complete for:
- Symmetric 3-VAS
- General 3-VAS
- Symmetric 4-VAS
- General 4-VAS

Significance and Claims
The paper claims to settle the exact complexity of the reachability problem for 3-VAS and 4-VAS, as well as their symmetric fragments, resolving a long-standing gap where the problem was known only to be between NP and PSPACE.

The authors note that the reduction technique used to prove Theorem 1 does not become substantially harder due to the symmetry constraint. This suggests that symmetric VASS may serve as a useful intermediate model for studying decision problems in low-dimensional VAS.

However, the paper explicitly states that these techniques do not appear to extend to two-dimensional VAS. Consequently, the complexity of reachability for 2-VAS and symmetric 2-VAS remains open, currently known only to lie between NP and PSPACE. The authors frame this as an open question (Question 6) regarding the complexity of bounded 1-VAS, symmetric 2-VAS, and general 2-VAS.

The Puzzle of the Three-Counter Machine

The Big Discovery: It's a "PSPACE" Problem

What This Means for the Rest of the World

The One Mystery Left Behind

Technical Summary: Reachability in 3-VAS⋆

More like this