Lower Bounds for the Reachability Problem in Fixed Dimensional VASSes

We study the complexity of the reachability problem for Vector Addition Systems with States (VASSes) in fixed dimensions. We provide four lower bounds improving the currently known state-of-the-art: 1) NP-hardness for unary flat 3-VASSes (VASSes in dimension 3), 2) PSpace-hardness for unary 5-VASSes, 3) ExpSpace-hardness for binary 6-VASSes and 4) Tower-hardness for unary 8-VASSes. On the presentation I plan to tell a few words about 1) the results, 2) techniques, which we have used, 3) motiviations to study low dimensional VASSes, and 4) important challenges, which remain for the future. Previous version of this work was submitted to LICS 2022, a co-autor is Łukasz Orlikowski. The work is on arXiv.

Authors

• Wojciech Czerwiński

Keywords

No keywords are indexed for this paper.