The Reachability Problem for Petri Nets is Not Primitive Recursive
Not on the map. Why?
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.
Key facts. Cited by 5 papers in the map (data through 7 Oct 2026). First posted on arXiv 26 Apr 2021.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2021: 1; 2022: 1; 2023: 0; 2024: 0; 2025: 1; 2026: 2.
5 papers.
- 2026TCS-BENCH: Benchmarking State-of-the-Art Generative AI Theoretical Computer Science Research Abilitycited by 3
- 2021Improved Ackermannian lower bound for the Petri nets reachability problemcited by 2
- 2025Reachability in Symmetric VASScited by 1
- 2022Solvability of orbit-finite systems of linear equationscited by 0
- 2026Reachability in 3-VAScited by 0
- 2026TCS-BENCH: Benchmarking State-of-the-Art Generative AI Theoretical Computer Science Research Ability10 Aug 2026
- 2026Reachability in 3-VAS5 Aug 2026
- 2025Reachability in Symmetric VASS30 Jun 2025
- 2022Solvability of orbit-finite systems of linear equations22 Jan 2022
- 2021Improved Ackermannian lower bound for the Petri nets reachability problem18 May 2021