Lower Bounds for the Reachability Problem in Fixed Dimensional VASSes

Title:Lower Bounds for the Reachability Problem in Fixed Dimensional VASSes

Authors:Wojciech Czerwiński and Łukasz Orlikowski

Conference:LICS 2022

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

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.

Lower Bounds for the Reachability Problem in Fixed Dimensional VASSes

1

3

5

7

9

11

13

15

17

19

21

23

25

27

29

31

33

35

37

39

41

43

45

47

49

51

53

55

57

59

61

63

65

67

69

1of69

1

2

3

4