Complexity, Parallel Computation and Statistical Physics

The intuition that a long history is required for the emergence of complexity in natural systems is formalized using the notion of {\em depth } (related to Bennett's {\em logical depth}). The depth of a system is defined in terms of the number of parallel computational steps needed to simulate it. Depth provides an objective, irreducible measure of history applicable to systems of the kind studied in statistical physics. The talk will review concepts of parallel computational complexity theory and then present results for the depth of several well-known model systems in non-equilibrium statistical physics. It is argued that physical complexity cannot occur in the absence of substantial depth and that depth is a useful proxy for physical complexity.