# The Reachability Problem for Petri Nets is Not Primitive Recursive

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

## Key facts

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

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

- [TCS-BENCH: Benchmarking State-of-the-Art Generative AI Theoretical Computer Science Research Ability](https://mlsanity.com/paper/2608.09538/) (2026)
- [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)

We provide an Ackermannian complexity lower bound for the reachability problem for checking programs, a model equivalent to Petri nets. Moreover in fixed dimension 2d+4, we show that the problem is mathbbFd-hard. As a direct corollary, the reachability problem in dimension 10 is not elementary.