Lower Bounds for the Reachability Problem in Fixed Dimensional VASSes
| Autor: | Czerwiński, Wojciech, Orlikowski, Łukasz |
|---|---|
| Jazyk: | angličtina |
| Předmět: | |
| Zdroj: | Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science LICS '22: 37th Annual (ACM/IEEE) Symposium on Logic in Computer Science |
| DOI: | 10.1145/3531130.3533357 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|