The Complexity of Reachability in Affine Vector Addition Systems with States
share
We give a trichotomy on the complexity of integer reachability in vector addition systems with states extended with affine operations (affine VASS). Namely, we show that integer reachability in affine VASS is NP-complete for VASS with resets, PSPACE-complete for VASS with (pseudo-)transfers and VASS with (pseudo-)copies, and undecidable otherwise. We further present a dichotomy for standard reachability in affine VASS: it is decidable for VASS with permutations, and undecidable otherwise. This yields a complete and unified complexity landscape of reachability in affine VASS.
READ FULL TEXT