Abstract
Listed in the title (with time usually called, depending on the context, size or length, and depth sometimes called rank) are the most fundamental complexity measures of propositional proofs. Their original definitions are rather different, just as is the case with physical concepts they are named after. Nonetheless it turns out that there are many connections between these measures, many of them unexpected, intricate and difficult to prove.
In this talk we attempt to present these relations, both previously known and new, in the form of a combined and coherent picture based on an appropriate notion of simulation. We will also survey known separations, as well as present several important open problems that in many cases amount to proving super-critical trade-offs between some of these measures.
A significant part of the talk is based on joint work with Theodoros Papamakarios.