# Reachability in 3-VAS

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 20 references that are in the map.
- First posted on arXiv 5 Aug 2026.

## Builds on (most cited first, 8 of 8)

- [Reachability in Vector Addition Systems is Primitive-Recursive in Fixed Dimension](https://mlsanity.com/paper/1903.08575/) (2019)
- [The Reachability Problem for Petri Nets is Not Primitive Recursive](https://mlsanity.com/paper/2104.12695/) (2021)
- [The Reachability Problem for Petri Nets is Not Elementary](https://mlsanity.com/paper/1809.07115/) (2018)
- [Reachability in Vector Addition Systems is Ackermann-complete](https://mlsanity.com/paper/2104.13866/) (2021)
- [Reachability in Two-Dimensional Vector Addition Systems with States is PSPACE-complete](https://mlsanity.com/paper/1412.4259/) (2014)
- [Reachability in 3-VASS is Elementary](https://mlsanity.com/paper/2502.13916/) (2025)
- [Reachability in Symmetric VASS](https://mlsanity.com/paper/2506.23578/) (2025)
- [Improving Reachability in Vector Addition Systems through Pumpability](https://mlsanity.com/paper/2604.24095/) (2026)

## Abstract (arXiv)

We settle the exact complexity of the reachability problem in (stateless) vector addition systems (VAS) in fixed low dimension. In dimensions 2-4 it has only been known to be sandwiched between NP and PSPACE. We prove PSPACE-hardness of the reachability problem for symmetric vector addition systems in dimension 3 (3-VAS), a restricted fragment of general 3-VAS. Combined with previously established PSPACE upper bounds, our result settles the complexity of the problem to be PSPACE-complete in 3-VAS and 4-VAS, as well as in their symmetric fragments.