Blum axioms

The Blum axioms are two conditions on a computational complexity measure: it is defined exactly where its program computes, and deciding whether its value is below a given bound is computable.

Connect

Partial computable function: A function computed by an algorithm that may fail to halt on some inputs. The first axiom ties a measure’s domain to the inputs where its indexed program halts.
Computational complexity measure: A function assigning resource-cost values to indexed computations, subject to formal effectiveness conditions. Blum’s axioms define which abstract measures count as acceptable complexity measures.
Manuel Blum: A computer scientist known for foundational work in computational complexity and program verification. He introduced the axiomatic conditions for abstract complexity measures.
Big O notation: Asymptotic notation that bounds a function’s growth up to a constant factor. Blum measures can be compared asymptotically to state resource bounds and speedups.
Kolmogorov complexity: The length of the shortest program that outputs a given finite object. Unlike standard Blum measures, its bounded-value test is generally undecidable.
Gödel numbering: An effective assignment of natural-number codes to formal expressions or computational objects. Programs need indices so the axioms can state uniform conditions across computations.
Domain of a partial function: The set of inputs on which a partial function has a defined value. The first axiom makes the measure defined exactly when the indexed computation halts.
Computational complexity theory: The study of the resources required to solve computational problems. The axioms provide a machine-independent foundation for parts of this field.
Optimal algorithm: An algorithm that achieves the least possible resource use within a specified comparison framework. Blum’s speedup results show that some functions lack a single asymptotically optimal program.
Algorithmic information theory: The study of information content defined through computation and program descriptions. It studies program-size notions related to complexity but distinct from Blum’s resource measures.