Improved Lower Bounds for the Reachability Problem in Fixed Dimensional VASSes

Prelegent(ci)

Łukasz Orlikowski

Afiliacja

MIM UW

Termin

19 stycznia 2022 14:15

Pokój

p. 5050

Seminarium

Seminarium „Teoria automatów”

---

Complexity of the reachability problem in Vector Addition Systems (VASes) was a long standing problem for a few decades. Despite settling the computational complexity of the reachability problem in VASSes to be Ackermann-complete a lot of questions about VASSes remain to be solved. Even the reachability problem is not fully understood and the most clear evidence for that is the existence of big complexity gaps for the problem in small fixed dimensions. I will present you a joint work with Wojciech Czerwiński showing four new lower bounds for the reachability problem in fixed dimensional VASSes: 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 4) Tower-hardness for binary 8-VASSes

---