Reachability in 3-VASS is Elementary

Wojciech Czerwiński, Ismaël Jecker, Sławomir Lasota, Łukasz Orlikowski · 2025

Read Reachability in 3-VASS is Elementary by Wojciech Czerwiński, Ismaël Jecker, Sławomir Lasota, Łukasz Orlikowski (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-13916.txt.

Introduction

Can a machine with three counters and a few states reach a set state from another? Wojciech Czerwiński and three co-authors bound that puzzle's cost in 2025. It was known to be at least as hard as a space class, and at most in a tower class — a vast gap.

The team closes most of it: the puzzle fits in double-exponential space. The key is a path bound. If any path joins two states, a short one does, of at most triple-exponential length. Their route leans on a fresh trick: the reach sets of two-counter machines can be sketched by small, tidy sets. Small cases of big puzzles are how the field learns where the true wall stands.

Catalog record

CREATORWojciech Czerwiński, Ismaël Jecker, Sławomir Lasota, Łukasz Orlikowski
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE67 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-13916

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Reachability in 3-VASS is Elementary Wojciech Czerwiński, Ismaël Jecker, Sławomir Lasota, Łukasz Orlikowski Abstract The reachability problem in 3-dimensional vector addition systems with states (3-VASS) is known to be PSpace-hard, and to belong to Tower. We significantly narrow down the complexity gap by proving the problem to be solvable in doubly-exponential space. The result follows from a new upper bound on the length of the shortest path: if there is a path between two configurations of a 3-VASS then there is also one of at most triply-exponential length. We show it by introducing a novel technique of approximating the reachability sets of 2-VASS by small semi-linear sets. University of Warsaw [email protected] https://orcid.org/0000-0002-6169-868X Supported by the ERC grant INFSYS, agreement no. 950398. FEMTO-ST, CNRS, Univ. Franche-Comté, France [email protected] University of Warsaw [email protected] https://orcid.org/0000-0001-8674-4470 Supported by the ERC grant INFSYS, agreement no. 950398 and by the NCN grant 2021/41/B/ST6/00535. University of Warsaw [email protected] https://orcid.org/0009-0001-4727-2068 Supported by the ERC grant INFSYS, agreement no. 950398. ccs Theory of computation Parallel computing models keywords vector addition systems, Petri nets, reachability problem, dimension three, doubly exponential space, length of shortest path † † runningauthor: W. Czerwiński, I. Jecker, S. Lasota, and Ł. Orlikowski † † copyright: Wojciech Czerwiński, Ismaël Jecker, Sławomir Lasota, and Łukasz Orlikowski 1 Introduction Petri nets are an established model of concurrent systems with extensive applications in various areas of theoretical computer science. For most algorithmic questions, the model is equivalent to vector addition systems with states ( vass in short). A d -dimensional vass ( d - vass in short) is a finite automaton equipped additionally with a finite number d of nonnegative integer counters that are updated by transitions, under the proviso that the counter values can not drop below zero. Importantly, vass have no capability to zero-test counters, and hence the model is not Turing-complete. One of the central algorithmic problems for VASS is the reachability problem which asks, if in a given vass there is a path (a sequence of executions of transitions) from a given source configuration (consisting of a state together with counter values) to a given target configuration: vass reachability problem Input: vass V , source and target configurations s,t . Question: Is there a path from s to t ? Already in 1976, the problem was shown to be ExpSpace -hard by Lipton [ 21 ] , and few years later decidability was shown by Mayr [ 22 ] . Later improvements [ 15 , 16 ] simplified the construction, but no complexity upper bound was given until Leroux and Schmitz showed that the problem can be solved in Ackermannian complexity [ 18 , 19 ] . At the same time the lower bound was lifted to Tower -hardness [ 8 ] , and soon afterwards, in 2021, improved to Ackermann -hardness [ 17 , 9 ] . Although the complexity of the reachability problem is now settled to be Ackermann -complete, various complexity questions remain still widely open. One of them is the complexity of the reachability problem parametrised by dimension, namely in d -dimensional vass ( d - vass ) for fixed d\in\mathbb{N} . Although the question has been investigated for a few decades, exact bounds are only known for dimensions 1 and 2 (both for unary or binary representations of numbers in counter updates). In the case of binary encoding, the reachability problem is NP -complete for 1 - vass [ 12 ] and PSpace -complete for 2 - vass [ 2 ] , and in case of unary encoding the problem is NL -complete both for 1 - vass (folklore) and for 2 - vass [ 10 ] . For higher dimension almost nothing is known. All the upper complexity bounds for dimension 1 or 2 were obtained by estimating the length of the shortest path, or of its representation. For unary 1 - vass , it is a folklore that if there is a path between two configurations then there is also one of polynomial length (see [ 3 ] for more demanding quadratic upper bound), which implies NL -completeness. For binary 1 - vass , a polynomial-size representation of the shortest path was provided by [ 12 ] . Concerning binary 2 - vass , already in 1979 Hopcroft and Pansiot showed that the reachability sets of 2 - vass are effectively semi-linear, and therefore the reachability problem is decidable [ 13 ] . Subsequently, 2-ExpTime upper complexity bound for binary 2 - vass was established by [ 14 ] . In [ 20 ] Leroux and Sutre showed that even the reachability relation is semi-linear, and that the relation is flattable, namely that it can be described by a finite number of simple expressions called linear path schemes . Only in 2015, careful examination of these linear path schemes led to exponential upper bound on the length of the shortest path, and consequently to PSpace upper bound [ 2 ] . Concerning unary 2 - vass , polynomial upper bound on the length of the shortest path was shown [ 10 , 1 ] , thus yielding NL -completeness. Our understanding of the model drops drastically for dimensions larger than 2, as most of good properties admitted in dimension 1 or 2 vanish. For instance, already since the seminal paper [ 13 ] it is known that reachability sets of 3 - vass are not necessarily semi-linear. Investigation of 3 - vass was advocated by many papers cited above, e.g. [ 13 , 2 , 1 ] , but until now no specific complexity bounds for 3 - vass are known, except for generic parametric bounds known for d - vass in arbitrary fixed dimension d\geq 3 . By [ 19 ] , the reachability problem in d - vass is in \mathcal{F}_{d+4} , 1 1 1 The complexity class \mathcal{F}_{i} corresponds to the i -th level of Grzegorczyk’s fast-growing hierarchy [ 25 ] . later improved to \mathcal{F}_{d} [ 11 ] . In case of 3 - vass , this yields membership in \mathcal{F}_{3}=\textsc{Tower} . On the other hand, no lower bound is known for binary 3 - vass except for the PSpace lower bound inherited from binary 2 - vass (for unary 3 - vass , NP -hardness has been recently shown by [ 4 ] ). The complexity gaps remains thus huge, namely between PSpace and Tower . As our main result, we narrow down this gap significantly. Contribution. In this paper we investigate complexity of the reachability problem in 3 - vass . Our main result is the first elementary upper complexity bound for the problem: Theorem 1 . The reachability problem in 3 - vass is in 2-ExpSpace , under binary encoding. In particular, this refutes the natural conjecture that for every d\geq 3 , the reachability problem for d - vass is \mathcal{F}_{d} -complete and provides the first algorithm, which solves the problem for vass with finite reachability sets faster than exhaustive search. Our way to prove Theorem 1 is by bounding triply-exponentially the length of the shortest path between the given source and target configurations. This main technical result, formulated in Lemma 2 below, applies to sequential 3 - vass ,

Read the complete text