Blum axioms

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.

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

Definition

To begin, we list all partially computable functions. That is, we assign a computable numbering of these functions: $\varphi _{0},\varphi _{1},\dots$. For example, we may specify a specific programming language, then assign $\varphi _{n}$ to be the lexicographically n-th syntactically valid program according to that. Two programs $\varphi _{n},\varphi _{m}$ may compute the exact same partial function, but have different numberings. This allows us to distinguish their "complexity"

Abstractly, to say that we are measuring the "complexity" of program $\varphi _{n}$ means finding a function $\Phi _{n}$, such that for any program input $x$, the complexity/cost of computing $\varphi _{n}$ on that input is $\Phi _{n}(x)$. If program $\varphi _{n}$ does not halt on $x$, then $\Phi _{n}(x)$ should be undefined. Otherwise, $\Phi _{n}(x)$ should be a definite natural number. This gives us the first axiom:

• The domains of $\varphi _{i}$ and $\Phi _{i}$ are identical.

Further, the complexity measure should be computable in some sense, for non-computable complexity measures is not interesting in practice. This gives us the second axiom:

• There is a program that, given any $i,x,c\in \mathbb {N}$, decides whether $\Phi _{i}(x)\leq c$. Note that if $\Phi _{i}(x)$ is undefined, then by definition $\Phi _{i}(x)\leq c$ is FALSE for all $c\in \mathbb {N}$. In other words, the set $\{(i,x,c)\in \mathbb {N} ^{3}|\Phi _{i}(x)=c\}$ is recursive.

These are the Blum axioms. A Blum complexity measure is a pairing $(\varphi ,\Phi )$ that satisfies the Blum axioms.

Examples

Time complexity is a Blum complexity measure. To decide whether $\Phi _{i}(x)\leq c$, simulate $\varphi _{i}(x)$ for $c$ steps. If the machine halts before $c$ steps are done, then output TRUE, else output FALSE.

Similarly, space complexity, or computable combinations thereof, is a Blum complexity measure.

$(\varphi ,\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):=\{\varphi _{i}\in \mathbf {P} ^{(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.

References

• Boas, Peter van Emde (1975), Bečvář, Jíří (ed.), "Ten years of speedup", Mathematical Foundations of Computer Science 1975 4th Symposium, Mariánské Lázně, September 1–5, 1975, vol. 32, Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 13–29, doi:10.1007/3-540-07389-2_179, ISBN 978-3-540-07389-5
• Bridges, Douglas S. (1994), "Abstract Complexity Theory", Computability, vol. 146, New York, NY: Springer New York, pp. 93–115, doi:10.1007/978-1-4612-0863-1_7, ISBN 978-1-4612-6925-0
• Smith, Carl H. (1994), "Abstract Complexity Theory", A Recursive Introduction to the Theory of Computation, New York, NY: Springer New York, pp. 68–90, doi:10.1007/978-1-4419-8501-9_4, ISBN 978-1-4612-6420-0