# Reachability in Vector Addition Systems is Ackermann-complete

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Apr 2021.

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

- [Improved Ackermannian lower bound for the Petri nets reachability problem](https://mlsanity.com/paper/2105.08551/) (2021)
- [Reachability in Symmetric VASS](https://mlsanity.com/paper/2506.23578/) (2025)
- [Solvability of orbit-finite systems of linear equations](https://mlsanity.com/paper/2201.09060/) (2022)
- [Reachability in 3-VAS](https://mlsanity.com/paper/2608.04786/) (2026)

## Abstract (arXiv)

Vector Addition Systems and equivalent Petri nets are a well established models of concurrency. The central algorithmic problem for Vector Addition Systems with a long research history is the reachability problem asking whether there exists a run from one given configuration to another. We settle its complexity to be Ackermann-complete thus closing the problem open for 45 years. In particular we prove that the problem is Fk-hard for Vector Addition Systems with States in dimension 6k, where Fk is the k-th complexity class from the hierarchy of fast-growing complexity classes.