Unifying lower bounds for algebraic machines, semantically

Thomas Seiller, Luc Pellissier, Ulysse Léchine

This paper presents a new abstract method for proving lower bounds in computational complexity. Based on the notion of topological and measurable entropy for dynamical systems, it…