Improved Lower Bounds for Reachability in Vector Addition Systems
Wojciech Krzysztof Czerwinski, Sławomir Lasota, Lukasz Orlikowski · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2021
We investigate computational complexity of the reachability problem for vector addition systems (or, equivalently, Petri nets), the central algorithmic problem in verification of concurrent systems. Concerning its complexity, after 40 years of stagnation, a non-elementary lower bound has been shown recently: the problem needs a tower of exponentials of time or space, where the height of tower is linear in the input size. We improve on this lower bound, by increasing the height of tower from linear to exponential. As a side-effect, we obtain better lower bounds for vector addition systems of fixed dimension.