# Reachability in 3-VASS is Elementary

arXiv: https://arxiv.org/abs/2502.13916 · HTML: https://mlsanity.com/paper/2502.13916/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Feb 2025.

## Built on by (most cited first, 1 of 1)

- [Reachability in 3-VAS](https://mlsanity.com/paper/2608.04786/) (2026)

## Abstract (arXiv)

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.