  We study the complexity of reachability problems on branching extensions of
vector addition systems, which allows us to derive new non-elementary
complexity bounds for fragments and variants of propositional linear logic. We
show that provability in the multiplicative exponential fragment is Tower-hard
already in the affine case -- and hence non-elementary. We match this lower
bound for the full propositional affine linear logic, proving its
Tower-completeness. We also show that provability in propositional contractive
linear logic is Ackermann-complete.
