Algorithmic complexity
Algorithmic complexity is a term that carries two distinct but cognate meanings in the study of computation and information. In the tradition of Kolmogorov complexity, it denotes the length of the shortest effective description of an individual object — the minimum program that would generate a given string, pattern, or structure. In the tradition of computational complexity theory, it denotes the resources — time, space, memory, communication — that an algorithm requires to solve a problem as a function of input size. These two traditions arose independently, yet they converge on a single question: what does it cost, in information or in computation, to produce or process a given structure?
Descriptive Complexity
The descriptive tradition, inaugurated by Kolmogorov, Solomonoff, and Chaitin, treats complexity as a property of objects rather than of problems. A string of a million zeros is simple because a short program generates it; a random string of the same length is complex because no compression is possible. The defining result is that this measure is uncomputable: no algorithm can determine the shortest description of an arbitrary input. This places algorithmic complexity at the intersection of Gödel's incompleteness, the Halting Problem, and the foundations of information theory.
Where Shannon Entropy measures average information across a probability distribution, Kolmogorov complexity measures the information content of a single object. The gap between the two — the difference between average description length and minimum description length — is where the phenomenon of Emergence becomes formally tractable. A system with simple update rules (short Kolmogorov complexity) can generate behavior whose description is incompressible (high apparent complexity). The emergence of complex behavior from simple rules is not metaphorical; it is a theorem about the growth of algorithmic descriptions under iterated computation.
Resource-Bounded Complexity
The resource-bound tradition, inaugurated by Hartmanis and Stearns, treats complexity as a property of problems and the algorithms that solve them. It asks not how complex a given object is, but how much computation is required to recognize, construct, or decide properties of objects. The classification of problems into complexity classes — P, NP, PSPACE, and beyond — is the architecture of computational limits. Time complexity measures temporal cost; Space complexity measures memory cost. The two are not independent: every time bound implies a space bound, and every space bound implies an exponential time bound.
The two traditions are not merely parallel. They are structurally related. The uncomputability of Kolmogorov complexity means that any attempt to compute it exactly requires unbounded resources. Conversely, any resource-bound on computation imposes a bound on what can be compressed or described. Resource-bounded Kolmogorov complexity is the formal bridge: it asks for the shortest description that can be generated within a given time or space budget. The complexity of an object depends on the resources available to describe it.
Complexity as a Unifying Lens
When these two traditions are brought together, algorithmic complexity becomes a lens for understanding systems at multiple scales. In AIXI, the theoretically optimal learning agent, hypotheses are weighted by their Kolmogorov complexity — simplicity as a proxy for prior probability. In machine learning, practical algorithms approximate this ideal by limiting hypothesis space to what is computable within resource constraints. The gap between the ideal (unbounded Kolmogorov complexity) and the practical (resource-bounded approximation) is the defining tension of artificial intelligence.
The same tension appears in natural systems. Complex adaptive systems — brains, economies, ecosystems — operate under severe resource constraints. They cannot compute optimal solutions; they approximate. The structures that survive are those that achieve sufficient complexity (descriptive richness) within feasible computational costs (resource limits). Algorithmic complexity, in both its senses, is therefore not merely a technical tool but a conceptual framework for asking why certain structures persist and others do not.
The unification of descriptive and resource-bound complexity is not a philosophical convenience. It is a diagnostic. Any field that treats complexity as a single scalar — whether information content or computational cost — is missing the interaction between what a system is and what it can afford to compute. The brain does not maximize Kolmogorov complexity; it maximizes the ratio of behavioral complexity to metabolic cost. Evolution does not optimize algorithms; it optimizes algorithms under thermal, temporal, and energetic constraints. A theory of complexity that ignores resource bounds is not a theory of natural systems. It is a theory of Platonic ideals — beautiful, rigorous, and irrelevant.