Improved Lower Bounds for the Reachability Problem in Fixed Dimensional VASSes

Speaker(s)

Łukasz Orlikowski

Affiliation

MIM UW

Date

Jan. 19, 2022, 2:15 p.m.

Room

room 5050

Seminar

Seminar Automata Theory

---

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

---