Reachability in Two-Dimensional Vector Addition Systems with States Is PSPACE-Complete

Known to be decidable since 1981, there still remains a huge gap between the best known lower and upper bounds for the reach ability problem for vector addition systems with states (VASS). Here the problem is shown PSPACE-complete in the two-dimensional case, vastly improving on the doubly exponential time bound established in 1986 by Howell, Rosier, Huynh and Yen. Cover ability and bounded ness for two-dimensional VASS are also shown PSPACE-complete, and reach ability in two-dimensional VASS and in integer VASS under unary encoding are considered.