Reachability in 3-VAS
Łukasz Kamiński, Sławomir Lasota
cs.CL
Submitted: 2026-08-05
License: http://creativecommons.org/licenses/by/4.0/
The gist: We settle the exact complexity of the reachability problem in (stateless) vector addition systems (VAS) in fixed low dimension.
Terminology
Abstract
We settle the exact complexity of the reachability problem in (stateless) vector addition systems (VAS) in fixed low dimension. In dimensions 2-4 it has only been known to be sandwiched between NP and PSPACE. We prove PSPACE-hardness of the reachability problem for symmetric vector addition systems in dimension 3 (3-VAS), a restricted fragment of general 3-VAS. Combined with previously established PSPACE upper bounds, our result settles the complexity of the problem to be PSPACE-complete in 3-VAS and 4-VAS, as well as in their symmetric fragments.
Sources
Related papers
- Exploring Solution Divergence and Its Effect on Large Language Model Problem Solving
- Ishigaki-IDS-Bench: A Benchmark for Generating Information Delivery Specification from BIM Information Requirements
- Subliminal Steering: Stronger Encoding of Hidden Signals
- MedStruct-S: A Benchmark for Key Discovery, Key-Conditioned QA and Semi-Structured Extraction from OCR Clinical Reports
- The End of Transformers? On Challenging Attention and the Rise of Sub-Quadratic Architectures
- Untangling the Mechanisms of Misleading Context in Medical Question Answering