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

Definition

To begin, we list all partial 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.

Given a Blum complexity measure, and any total computable function $f$ , we define $C[f]$ to be the class of functions of complexity class bounded by $f$ . That is, $C[f]$ consists of total computable functions $\phi$ , such that there exists some $\varphi _{n}$ , such that $\forall x,\;\Phi _{n}(x)\leq f(x)$ .

The definition of complexity class is sometimes loosened to ${\bar {C}}[f]$ , the class of functions bounded by $f$ for almost all inputs. That is, ${\bar {C}}[f]$ consists of total computable functions $\phi$ , such that there exists some $\varphi _{n}$ , such that $\Phi _{n}(x)\leq f(x)$ for all but finitely many $x$ .

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.

Properties

All statements assume begin with "For any Blum complexity measure $(\varphi ,\Phi )$ ...".

There are arbitrarily difficult ways of computing any function: Any total computable $f$ , and any partial computable $\phi$ , there exists some $\varphi _{n}$ such that $\phi =\varphi _{n}$ , and for any $x$ , if $\varphi _{n}(x)$ is defined, then $\Phi _{n}(x)>h(x)$ .^[2]^{: Thm. 3.18}

There are functions that are arbitrarily high in complexity class: Any total computable $f$ , there exists total computable functions not in ${\bar {C}}[f]$ .^[2]^{: Thm. 3.20}

Blum's speedup theorem.

Gap theorem: Given any total computable $g$ , there exists a total computable function $f$ such that $C[f]=C[g\circ f]$ .

The construction is constructive. That is, the proof of the theorem is simply a program that, given a program for computing $f$ , outputs a program that computes $g$ .^[2]^{: Thm. 3.26}

The McCreight and Meyer union theorem:^[3] Let $f(n,x)$ be a total computable function, such that for any $n\in \mathbb {N}$ , $f(n+1,x)>f(n,x)$ for all but finitely many $x$ . Then there exists a total computable function $F$ such that $C[F]=\cup _{n\in \mathbb {N} }C[f(n,\cdot )]$ .

Compression theorem:^[2]^{: Thm. 3.28} Let $g(x,n)$ be a total computable function. There exists a total computable function $f$ such that, for any $n\in \mathbb {N}$ :

If $\varphi _{n}(x)$ is defined, then $\varphi _{f(n)}(x)<x$ . This condition is used to avoid trivially stacking up complexity in the output size.
For any program $m$ such that $\varphi _{m}=\varphi _{f(n)}$ , we have $\Phi _{m}(x)\geq \Phi _{n}(x)$ for almost all $x$ . This gives the universal lower bound.
$\Phi _{f(n)}(x)\leq g(x,\Phi _{n}(x))$ for almost all $x$ . This gives the existential upper bound.

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

^ Blum, Manuel (1967). "A Machine-Independent Theory of the Complexity of Recursive Functions" (PDF). Journal of the ACM. 14 (2): 322–336. doi:10.1145/321386.321395. S2CID 15710280.
^ ^a ^b ^c ^d 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
^ McCreight, E. M.; Meyer, A. R. (1969-05-05). "Classes of computable functions defined by bounds on computation: Preliminary Report". Proceedings of the first annual ACM symposium on Theory of computing. STOC '69. New York, NY, USA: Association for Computing Machinery: 79–88. doi:10.1145/800169.805423. ISBN 978-1-4503-7478-1.

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

[1] Blum, Manuel (1967). "A Machine-Independent Theory of the Complexity of Recursive Functions" (PDF). Journal of the ACM. 14 (2): 322–336. doi:10.1145/321386.321395. S2CID 15710280.

[:0-2] 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

[3] McCreight, E. M.; Meyer, A. R. (1969-05-05). "Classes of computable functions defined by bounds on computation: Preliminary Report". Proceedings of the first annual ACM symposium on Theory of computing. STOC '69. New York, NY, USA: Association for Computing Machinery: 79–88. doi:10.1145/800169.805423. ISBN 978-1-4503-7478-1.

[1]

[2]

[3]