Lower Bounds for the Reachability Problem in Fixed Dimensional VASSes

2022/03/08 by Wojciech Czerwiński, Czerwiński, Wojciech, Łukasz Orlikowski +1
Computer Science · Engineering · #Complexity and Algorithms in Graphs #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Formal Methods in Verification #Logic in Computer Science (cs.LO) #Radiation Effects in Electronics

paper · pdf · doi:10.48550/arxiv.2203.04243

openalex publication_date 2022/03/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Related

• Improved Algorithm for Reachability in d-VASS
• New Lower Bounds for Reachability in Vector Addition Systems
• Reachability in Geometrically d-Dimensional VASS
• Reachability in 3-VASS is Elementary
• Reachability in fixed dimension vector addition systems with states