Lower Bounds for the Reachability Problem in Fixed Dimensional VASSes

Wojciech Czerwinski; Lukasz Orlikowski

doi:10.1145/3531130.3533357

LICS2022顶会

Lower Bounds for the Reachability Problem in Fixed Dimensional VASSes

Wojciech Czerwinski, Lukasz Orlikowski

arXiv DOI 出版方

2022年份

6被引次数

2顶会引用

摘要

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 4-VASSes (VASSes in dimension 4), 2) PSpace-hardness for unary 5-VASSes, 3) ExpSpace-hardness for binary 6-VASSes and 4) Tower-hardness for unary 8-VASSes.