Blum axioms

In

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 ${\displaystyle (\varphi ,\Phi )}$ with ${\displaystyle \varphi }$ a

${\displaystyle \mathbf {P} ^{(1)}}$ and a computable function

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

which satisfies the following Blum axioms. We write ${\displaystyle \varphi _{i}}$ for the i-th

under the Gödel numbering ${\displaystyle \varphi }$, and ${\displaystyle \Phi _{i}}$ for the partial computable function ${\displaystyle \Phi (i)}$.

• the domains of ${\displaystyle \varphi _{i}}$ and ${\displaystyle \Phi _{i}}$ are identical.
• the set ${\displaystyle \{(i,x,t)\in \mathbb {N} ^{3}|\Phi _{i}(x)=t\}}$ is recursive.

Examples

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

Complexity classes

For a

${\displaystyle f}$ complexity classes of computable functions can be defined as

${\displaystyle C(f):=\{\varphi _{i}\in \mathbf {P} ^{(1)}|\forall x.\ \Phi _{i}(x)\leq f(x)\}}$

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

${\displaystyle C(f)}$ is the set of all computable functions with a complexity less than ${\displaystyle f}$. ${\displaystyle C^{0}(f)}$ is the set of all boolean-valued functions with a complexity less than ${\displaystyle f}$. If we consider those functions as indicator functions on sets, ${\displaystyle C^{0}(f)}$ can be thought of as a complexity class of sets.

References