Effective Complexity and Its Relation to Logical Depth

Effective complexity measures the information content of the regularities of an object. It has been introduced by Gell-Mann and Lloyd to avoid some of the disadvantages of Kolmogorov complexity. In this paper, we derive a precise definition of effective complexity in terms of algorithmic information theory. We analyze rigorously its basic properties such as effective simplicity of incompressible binary strings and existence of strings that have effective complexity close to their lengths. Since some of the results have appeared independently in the context of algorithmic statistics by Gacs , we discuss the relation of effective complexity to the corresponding complexity measures, in particular to Kolmogorov minimal sufficient statistics. As our main new result we show a remarkable relation between effective complexity and Bennett's logical depth: If the effective complexity of a string x exceeds a certain explicit threshold then that string must have astronomically large depth; otherwise, the depth can be arbitrarily small.