Search papers, labs, and topics across Lattice.
This paper establishes the exact complexity of the reachability problem in symmetric vector addition systems (VAS) in dimensions 3 and 4, proving that it is PSPACE-complete. Prior to this work, the complexity was only known to lie between NP and PSPACE, leaving a significant gap in understanding. The authors demonstrate PSPACE-hardness for 3-VAS, thereby confirming the complexity classification for both 3-VAS and 4-VAS, including their symmetric variants.
PSPACE-completeness of the reachability problem in 3-VAS reveals a crucial boundary in computational complexity that was previously unresolved.
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.
