Journal of Statistical Physics, Vol. 114, Nos. 3/4, February 2004. p. 1127-1137.
We construct a complexity measure from first principles, as an average over the "obstruction against prediction" of some observable that can be chosen by the observer. Our measure evaluates the variability of the predictability for characteristic system behaviors, which we extract by means of the thermodynamic formalism. Using theoretical and experimental applications, we show that "complex" and "chaotic" are different notions of perception. In comparison to other proposed measures of complexity, our measure is easily computable, non-divergent for the classical 1-d dynamical systems, and has properties of non-overuniversality. The measure can also be computed for higher-dimensional and experimental systems, including systems composed of different attractors. Moreover, the results of the computations made for classical 1-d dynamical systems imply that it is not the nonhyperbolicity, but the existence of a continuum of characteristic system length scales, that is at the heart of complexity.