Blum axioms explained

In computational complexity theory the Blum axioms or Blum complexity axioms are axioms that specify desirable properties of complexity measures on the set of computable functions. The axioms were first defined by Manuel Blum in 1967.^[1]

Importantly, Blum's speedup theorem and the Gap theorem hold for any complexity measure satisfying these axioms. The most well-known measures satisfying these axioms are those of time (i.e., running time) and space (i.e., memory usage).

Definitions

A Blum complexity measure is a pair

(\varphi, \Phi) with \varphi a numbering of the partial computable functions P ^{(1)} and a computable function\Phi: N \to P ^{(1)} which satisfies the following Blum axioms. We write \varphi _{i} for the i-th partial computable function under the Gödel numbering \varphi , and \Phi _{i} for the partial computable function \Phi(i) .

• the domains of

\varphi _{i} and \Phi _{i} are identical.

• the set

\{(i,x,t) \in N ^{3} | \Phi _{i(x)} = t\} is recursive.

Examples

(\varphi, \Phi) is a complexity measure, if \Phi is either the time or the memory (or some suitable combination thereof) required for the computation coded by i.(\varphi, \varphi) is not a complexity measure, since it fails the second axiom.

Complexity classes

f complexity classes of computable functions can be defined asC(f) : = \{ \varphi _{i} \in P ^{(1)} | \forall x. \Phi _{i(x)} \leq f(x) \} C ^{0(f)} : = \{ h \in C(f) | codom (h) \subseteq \{ 0 , 1 \} \} C(f) is the set of all computable functions with a complexity less than f . C ^{0(f)} is the set of all boolean-valued functions with a complexity less than f . If we consider those functions as indicator functions on sets, C ^{0(f)} can be thought of as a complexity class of sets.

Notes and References

1. Blum . Manuel . Manuel Blum. A Machine-Independent Theory of the Complexity of Recursive Functions . 10.1145/321386.321395 . Journal of the ACM. 14 . 2 . 322–336. 1967 . 15710280 .