# Lower Bounds for the Reachability Problem in Fixed Dimensional VASSes

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Mar 2022.

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

- [Reachability in Symmetric VASS](https://mlsanity.com/paper/2506.23578/) (2025)

## Abstract (arXiv)

We study the complexity of the reachability problem for Vector Addition Systems with States (VASSes) in fixed dimensions. We provide four lower bounds improving the currently known state-of-the-art: 1) np-hardness for unary flat 4-VASSes (VASSes in dimension 4), 2) pspace-hardness for unary 5-VASSes, 3) expspace-hardness for binary 6-VASSes and 4) tower-hardness for unary 8-VASSes.