Lower Bounds for the Reachability Problem in Fixed Dimensional VASSes
Wojciech Czerwinski, Lukasz Orlikowski
2022Year
6Citations
2Top-tier citations
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.
Ask about this paper
Your agent reads all of it.
Lune indexed this paper to the last equation, along with the top-tier papers that cite it. Ask a question and the answer quotes them.
Your agent calls
Luneget_paper_fulltext
Free to start. No credit card required.
Terminal
Install the CLIlune papers fulltext 133e405e-7cad-4439-beac-c9ae0cba1a69Cited by top-tier papers2
- A Complexity Dichotomy for Semilinear Target Sets in Automata with One CounterYousef Shakiba, Henry Sinclair-Banks, Georg ZetzscheLICS 2025 · 4 citations
- The Tractability Border of Reachability in Simple Vector Addition Systems with StatesDmitry Chistikov, Wojciech Czerwinski, Filip Mazowiecki, Lukasz Orlikowski et al.FOCS 2024 · 1 citation
Builds on2
Related papers
- Reachability in VASS Extended with Integer CountersClotilde Bizière, Wojciech Czerwinski, Roland Guttenberg, Jérôme Leroux et al.LICS 2026
- The Complexity of Reachability in Affine Vector Addition Systems with StatesMichael Blondin, Mikhail A. RaskinLICS 2020 · 4 citations
- Reachability and Related Problems in Vector Addition Systems with Nested Zero TestsRoland Guttenberg, Wojciech Czerwinski, Slawomir LasotaLICS 2025 · 10 citations
- Reachability in Continuous Pushdown VASSA. R. Balasubramanian, Rupak Majumdar, Ramanathan S. Thinniyam, Georg ZetzschePOPL 2024 · 1 citation
- An Approach to Regular Separability in Vector Addition SystemsWojciech Czerwinski, Georg ZetzscheLICS 2020 · 4 citations
