mlsanityData to 14 Oct 2026

Reachability in 3-VAS

arXiv 2608.04786 ↗First posted 5 Aug 2026cs.CLcited by 0

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 8 of its 20 references that are in the map. First posted on arXiv 5 Aug 2026.

Builds on

8 of 20 references.

References · 8

  1. 2019Reachability in Vector Addition Systems is Primitive-Recursive in Fixed Dimensioncited by 5
  2. 2021The Reachability Problem for Petri Nets is Not Primitive Recursivecited by 5
  3. 2018The Reachability Problem for Petri Nets is Not Elementarycited by 4
  4. 2021Reachability in Vector Addition Systems is Ackermann-completecited by 4
  5. 2014Reachability in Two-Dimensional Vector Addition Systems with States is PSPACE-completecited by 3
  6. 2025Reachability in 3-VASS is Elementarycited by 1
  7. 2025Reachability in Symmetric VASScited by 1
  8. 2026Improving Reachability in Vector Addition Systems through Pumpabilitycited by 1

Built on by

Not cited yet.