The Reachability Problem for Petri Nets is Not Primitive Recursive

Abstract

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 ${\mathbb{F}}_d$-hard. As a direct corollary, the reachability problem in dimension 10 is not elementary.

Journal version of FOCS 2022