Resource-bounded Kolmogorov complexity

Resource-bounded Kolmogorov complexity is the length of the shortest program that produces a given object as output, under the constraint that the program must halt within a specified resource budget — typically time or space. It is the practical sibling of Kolmogorov complexity, which is uncomputable because it places no bound on the resources the describing program may consume. By restricting the computational budget, resource-bounded Kolmogorov complexity becomes computable and algorithmically tractable, at the cost of losing the machine-independence that makes standard Kolmogorov complexity so philosophically powerful.

The concept was developed by Leonid Levin and others as a bridge between the descriptive world of Kolmogorov complexity and the resource-bound world of computational complexity theory. Levin's universal search is the canonical algorithm: it enumerates all programs in order of increasing length, runs each for a bounded time, and returns the first program that produces the target output. This is not merely a theoretical construction; it is the logical structure of all practical learning algorithms, which search a hypothesis space under time and memory constraints.

The deeper significance of resource-bounded Kolmogorov complexity is epistemic. It formalizes the intuition that the complexity of an object depends not only on what the object is but on what resources are available to describe it. A protein fold may have a short description in the language of quantum chemistry but a very long description in the language of classical mechanics. The choice of resource bounds is therefore not a technical convenience; it is a modeling decision that determines what counts as simple and what counts as complex.

Resource-bounded Kolmogorov complexity exposes the hidden assumption in every claim about simplicity: simple for whom, and with what tools? The unbounded version pretends to answer this objectively, but its uncomputability makes it a fantasy of omniscience. The bounded version is honest: it admits that complexity is a relationship between an object, a description language, and a computational budget. This honesty is precisely why the bounded version is more useful for science and engineering — and why the unbounded version remains more seductive for philosophy.