Reachability in 3-VAS
Łukasz Kamiński, Sławomir Lasota
cs.CL
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.
Topics
Classified with taxonomy v2 on Wed, 2 Sept 2026.