💻 computer science

Reachability in Fixed-Dimensional Continuous VASS

This paper establishes a complexity dichotomy for the reachability and coverability problems in fixed-dimensional continuous Vector Addition Systems with States, proving that while all variants are solvable in $\mathsf{AC}^1$ for dimension 1, they become $\mathsf{NP}$ -complete for dimensions 2 and higher, utilizing a novel "Egyptian prime fractions" technique to demonstrate these results.

Original authors: Michal Ajdarów, A. R. Balasubramanian, Łukasz Orlikowski

Published 2026-06-30

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Michal Ajdarów, A. R. Balasubramanian, Łukasz Orlikowski

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 warehouse with a row of storage bins. In a standard warehouse (called a VASS in the paper), you can only move whole crates in and out. If a rule says "add 5 crates," you must add exactly 5. If you try to add 5.5, the system rejects it. The paper notes that figuring out if you can get from one specific arrangement of crates to another in this standard system is incredibly difficult—so hard that it belongs to a class of problems that grow explosively complex as the warehouse gets bigger.

To make things easier, researchers invented a "continuous" version of this warehouse, called CVASS. In this new version, you aren't stuck with whole crates. You can pour in "liquid" crates. You can add half a crate, a quarter, or even a tiny drop. You can choose a fraction (between 0 and 1) to scale any move. This makes the system much more flexible and, generally, much easier to analyze.

The Big Question
The authors of this paper asked: "If we limit the warehouse to a fixed, small number of bins (dimensions), does the difficulty of the problem change?"

They investigated two types of questions:

Reachability: Can we get from Point A to exactly Point B?
Coverability: Can we get from Point A to at least Point B (meaning we might have extra stuff in the bins, but we definitely have enough to cover the target)?

They looked at these questions under different rules (allowing negative liquid or not) and different ways of writing down the numbers (simple vs. complex). This created eight different variations of the problem.

The Main Discovery: A Sharp Divide
The paper reveals a surprising "tipping point" based on the number of bins:

1 Bin (Dimension 1): If you only have one bin, the problem is easy. No matter how you write the numbers or what rules you use, a computer can solve it very quickly. It's like solving a simple math puzzle.
2 or More Bins (Dimension 2+): As soon as you add a second bin, the problem suddenly becomes hard (specifically, "NP-complete"). It jumps from being a simple puzzle to a complex challenge that is as difficult as the hardest problems in this category.

The "Egyptian Prime" Trick
How did they prove that 2 bins are so hard? They used a clever trick they call the "Egyptian Prime Fractions" technique.

Imagine you want to encode a secret message (like a solution to a logic puzzle) into a single number.

They assigned a unique, large prime number to every variable in the puzzle (like $x_1$ , $x_2$ ).
They created a "recipe" where the total amount of liquid in the bin is the sum of fractions: $1/Prime_1 + 1/Prime_2$ , etc.
Because of how prime numbers work, there is only one unique way to build a specific sum using these specific fractions. It's like a fingerprint.

By setting up the warehouse rules so that the liquid level must match this unique "prime fingerprint" to succeed, they showed that solving the warehouse problem is exactly the same as solving a complex logic puzzle (3-SAT). If you can solve the warehouse, you can solve the logic puzzle. Since logic puzzles are hard, the warehouse problem is hard too.

The "Acyclic" Surprise
Usually, problems get harder when there are loops (cycles) in the rules, allowing you to repeat actions forever. However, the authors found that even if you remove all loops and make the warehouse a straight line (acyclic), the problem remains hard for 2 or more bins. This is the first time anyone has proven that a "straight-line" counter system with just two bins is this difficult.

What About Integer Rules?
The paper also looked at a stricter version where you can only move whole numbers (integers), not fractions.

1 Bin: Still easy.
2 Bins: Hard (but only if the numbers are written in a complex way).
3+ Bins: Hard, even with simple numbers.

The Takeaway
The paper draws a clear line in the sand:

1 Dimension: Easy.
2 Dimensions: Hard.

It turns out that adding just one extra dimension to these continuous systems creates a massive jump in complexity, turning a simple task into a computational nightmare, even when the system is simple and has no loops.

Technical Summary: Reachability in Fixed-Dimensional Continuous VASS

Problem Definition

This paper investigates the computational complexity of the reachability and coverability problems for Continuous Vector Addition Systems with States (CVASS) in fixed dimensions.

A CVASS is an over-approximation of standard VASS (or Petri nets) where counters store non-negative rational numbers rather than integers. Transitions can be fired fractionally: to fire a transition $t$ with update vector $w$ , one chooses a scaling factor $\alpha \in (0, 1]$ , updating the current state $u$ to $u + \alpha \cdot w$ . The paper considers two semantic variants:

$\mathbb{Q}$ -semantics: Counters can take any rational value (allowing negative intermediate values).
$\mathbb{Q}^+$ -semantics: Counters must remain non-negative throughout the execution.

The study focuses on systems with a fixed number of counters ( $d$ ), analyzing complexity under both unary and binary encodings of the input numbers. This yields eight distinct decision problems for each dimension (Reachability/Coverability $\times$ $\mathbb{Q}$ / $\mathbb{Q}^+$ $\times$ Unary/Binary). The paper also examines a restricted variant where transition vectors are restricted to integers.

Methodology

The authors employ a combination of graph-theoretic characterizations and novel reduction techniques to establish complexity bounds.

Upper Bounds (Dimension 1)

For 1-dimensional CVASS, the authors provide a precise characterization of reachability over the $\mathbb{Q}$ -semantics. They demonstrate that reachability depends on the existence of specific paths or "knots" (a path leading to a pumpable cycle and then to the target) in the underlying control graph.

Reduction Strategy: They first reduce $\mathbb{Q}^+$ -reachability to $\mathbb{Q}$ -reachability by handling interval constraints on counter values.
Algorithmic Approach: They show that checking the existence of these paths and knots can be performed in NL (Nondeterministic Logarithmic space) for integer updates and AC $^1$ (a subclass of P involving polynomial-size, logarithmic-depth circuits) for rational updates. This improves upon previous NC $^2$ bounds.

Lower Bounds (Dimensions $\ge$ 2)

To prove NP-hardness for dimensions $d \ge 2$ , the authors introduce a novel technique called the Egyptian prime fractions technique.

Encoding: They encode assignments of a 3-SAT formula into a single rational counter value. Each literal is assigned a distinct prime number $P(\ell)$ . An assignment is encoded as a sum of reciprocals of these primes (e.g., $\sum \frac{1}{P(\ell)}$ ).
Uniqueness: Leveraging the properties of prime numbers, they prove that this encoding is unique: distinct assignments yield distinct rational sums.
Reduction:
- Stage 1: They construct an acyclic 1-CVASS where an "assignment gadget" generates the encoded sum, and a "clause gadget" attempts to reduce this sum to zero by subtracting reciprocals corresponding to satisfied literals.
- Stage 2: To remove the "restricted run" assumption (where fractions must be 1) and move to coverability, they introduce a second counter. By modifying transitions to update a second counter such that the sum of both counters increases by exactly 1 per step, they force any valid coverability run to use fractions of exactly 1, effectively simulating the restricted 1-CVASS.
Zero-Tests: For the integer-update case in dimension 3, they simulate zero-tests (checking if a counter is exactly 0) using a third "controlling" counter, allowing them to reduce from 2-CVASS with zero-tests to 3-CVASS without zero-tests.

Key Contributions and Results

The paper provides a complete complexity dichotomy for the eight variants of the problem when transition vectors are over the rationals:

Dimension 1: All eight problems (Reachability/Coverability, $\mathbb{Q}$ $Q$ / $\mathbb{Q}^+$ $Q^{+}$ , Unary/Binary) are in AC $^1$ (and thus in P).
- Specifically, for integer updates over unary encoding, the problems are NL-complete.
Dimension $\ge$ 2: All eight problems are NP-complete.
- Crucially, this hardness holds even for acyclic CVASS (systems with no cycles in the control graph).

For the restricted case where transition vectors are integers:

Dimension 1: Problems are NL-complete (unary) or in AC $^1$ (binary).
Dimension 2: Problems are NP-complete (binary encoding).
Dimension $\ge$ 3: Problems are NP-complete (both unary and binary).

Significance and Claims

The authors claim several significant contributions to the theory of infinite-state systems:

First NP-Hardness for Acyclic Unary Systems: This work presents the first NP-hardness result for acyclic unary counter systems over fixed dimensions. Previously, hardness results for such restricted systems were not known.
Dimensional Threshold: The paper establishes a sharp complexity threshold at dimension 2. While 1-dimensional continuous systems are tractable (in AC $^1$ ), the complexity jumps to NP-complete as soon as the dimension reaches 2, regardless of whether the system is acyclic or the encoding is unary.
Egyptian Prime Fractions Technique: The introduction of this new technique for encoding propositional assignments into rational counters via sums of prime reciprocals is highlighted as a key methodological innovation enabling the hardness proofs.
Contrast with Standard VASS: The results contrast with standard VASS and some of its over-approximations, where coverability over unary encoding for fixed dimensions is known to be in NL. The continuous semantics, despite being an over-approximation, introduces sufficient complexity to make these problems NP-complete in dimension 2 and above.

The paper concludes that the continuous semantics, while useful for tractable analysis in 1D, becomes computationally intractable (NP-complete) in higher dimensions even under severe restrictions like acyclicity and unary encoding.