Lower Bounds for the Reachability Problem in Fixed Dimensional VASSes

EasyChair Preprint no. 8619

Abstract

We study the complexity of the reachability problem for Vector Addition Systems with States (VASSes) in fixed dimensions. We provide four lower bounds improving the currently known state-of-art: 1) NP-hardness for unary flat 4-VASSes (VASSes in dimension 4), 2) PSpace-hardness for unary 5-VASSes, 3) ExpSpace-hardness for binary 6-VASSes and 4) Tower-hardness for unary 8-VASSes.

Keyphrases: controlling counter, counter automata, fixed dimension, lower bounds, Petri nets, reachability problem, vector addition systems

@Booklet{EasyChair:8619,
  author = {Wojciech Czerwiński and Łukasz Orlikowski},
  title = {Lower Bounds for the Reachability Problem in Fixed Dimensional VASSes},
  howpublished = {EasyChair Preprint no. 8619},

  year = {EasyChair, 2022}}