Improved Ackermannian lower bound for the VASS reachability problem
share
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 Czerwiński 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 Czerwiński 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.
READ FULL TEXT