Blum axioms

From Wikipedia, the free encyclopedia

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

1 Definitions
- 1.1 Notes
- 1.2 Examples
2 Complexity classes
3 References

[edit] Definitions

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

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

which satisfies the following Blum axioms. We write $\varphi_i$ and $Φ i$ for the i-th partial computable function under the Gödel numbering $\varphi$ or $Φ$ .

the domain of $\varphi_i$ and the domain of $Φ i$ is identical.
the set $\{(i,x,t) \in \mathbf{N}^3 | \Phi_i(x) = t\}$ is recursive

[edit] Notes

A Blum complexity measure is defined using computable functions without any reference to a specific model of computation. In order to make the definition more accessible we rephrase the Blum axioms in terms of Turing machines:

A Blum complexity measure is a function $Φ$ mapping pairs $(M, x)$ to a natural number $\mathbb{N}$ or to infinity, where $M$ is a Turing Machine and $x$ is an input to $M$ . Furthermore, $Φ$ should satify the following axioms:

$Φ(M, x)$ is finite if and only if $M (x)$ halts
There is an algorithm which, on input $(M, x, n)$ decides if $Φ(M, x) = n$

[edit] Examples

$(\varphi, \Phi)$ is a complexity measure, if $Φ$ 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.

[edit] Complexity classes

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

$C(f) := \{ \varphi_i \in \mathbf{R}^{(1)} | \forall x \Phi_i(x) \leq f(x) \}$

$C^0(f) := \{ h \in C(f) | \mathrm{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.