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

Importantly, the Speedup and Gap theorems 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).

Blum axioms

---

A Blum complexity measure is a tuple $(\backslash varphi,\; \backslash Phi)$ with $\backslash varphi$ a Gödel numbering of the partial computable functions $\backslash mathbf\{P\}^\{(1)\}$ and a computable function

$\backslash Phi:\; \backslash mathbb\{N\}\; \backslash to\; \backslash mathbf\{P\}^\{(1)\}$

so that the following Blum axioms are satisfied

• for all $i\; \backslash in\; \backslash mathbb\{N\}$, $\backslash mathrm\{Dom\}(\backslash varphi\_i)\; =\; \backslash mathrm\{Dom\}(\backslash Phi\_i)$
• the set $\backslash \{(i,x,t)\; \backslash in\; \backslash mathbf\{N\}^3\; |\; \backslash Phi\_i(x)\; =\; t\backslash \}$ is recursive

Examples

---

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

Complexity classes

---

For a total computable function $f$ complexity classes of computable functions can be defined as

$C(f)\; :=\; \backslash \{\; \backslash varphi\_i\; \backslash in\; \backslash mathbf\{R\}^\{(1)\}\; |\; \backslash forall\; x\; \backslash Phi\_i(x)\; \backslash leq\; f(x)\; \backslash \}$

$C^0(f)\; :=\; \backslash \{\; h\; \backslash in\; C(f)\; |\; \backslash mathrm\{codom\}(h)\; \backslash subseteq\; \backslash \{0,1\backslash \}\; \backslash \}$

$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.

References

---

• M. Blum. "A machine-independent theory of the complexity of recursive functions". Journal of the ACM, 14(2):322 336, 1967.

Computational complexity theory | Mathematical axioms