Blum's axioms

Quick Reference

Two axioms in complexity theory, formulated by M. Blum. Let


be an effective enumeration of the Turing machines and let fi be the partial recursive function of a single variable that is computed by Mi. (For technical reasons it is simpler to think in terms of partial recursive functions than set (or language) recognizers.) if


is a sequence of partial recursive functions satisfying axiom 1:

fi(n) is defined if and only if Fi(n) is defined,

and axiom 2:

Fi(x) ≤ y is a recursive predicate of i, x, and y,

then Fi(n) is a computational complexity measure and can be thought of as the amount of some “resource” consumed by Mi in computing fi(n). This notion represents a useful abstraction of the basic resources — time and space. Several remarkable theorems about computational complexity have been proved for any measure of resources satisfying the two axioms (see gap theorem, speedup theorem).

Subjects: Computing.

Reference entries