Improved Ackermannian lower bound for the VASS reachability problem.
Sławomir Lasota · arXiv (Cornell University) · 2021
This draft is a follow-up of the Ackermannian lower bound for the reachability problem in vector addition systems with states (VASS), recently announced by Czerwinski and Orlikowski. Independently, the same result has been announced by Leroux, but with a significantly different proof. We provide a simplification of the former construction, thus improving the lower bound for VASS in fixed dimension: while Czerwinski and Orlikowski prove $F_k$-hardness in dimension $6k$, and Leroux in dimension $4k+9$, the simplified construction yields $F_k$-hardness already in dimension $3k+2$.