Reachability in Five-Dimensional Vector Addition Systems Is PSPACE-Complete
In the authors' words
Vector addition systems (VAS) are a fundamental model of concurrent computation in which transitions update nonnegative integer counters by adding integer vectors, provided all counters remain nonnegative. Closely related to Petri nets, VAS are the single-state counterpart of vector addition systems with states (VASS), which use finitely many states to restrict the available transitions. A classical simulation of -VASS by -VAS connects their reachability problems, but the complexity-theoretic picture of fixed-dimensional VAS remains largely unclear. While reachability in -VASS is PSPACE-complete under binary encoding, the best known upper bound for -VAS was only elementary. We prove that every reachable -VAS instance has a reachability witness of length polynomial in its unary size. Consequently, -VAS reachability is NL-complete under unary encoding and PSPACE-complete under binary encoding. We also establish a polynomial factorization of the reachability relation of every -VAS with . For -VAS, this strengthens Hopcroft and Pansiot's effective semilinearity of reachability sets to the full reachability relation. For every fixed , it also yields an upper bound for reachability in -VAS.
Appeared: Friday, October 30. arXiv. Preprint, not yet peer-reviewed.
Authors' comment: 69 pages,1 figure