Blum axioms

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: ${\displaystyle {\phi }_0,{\phi }_1,\dots }$. For example, we may specify a specific programming language, then assign ${\displaystyle {\phi }_n}$ to be the length-lexicographically n-th syntactically valid program according to that. Two programs ${\displaystyle {\phi }_n,{\phi }_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 ${\displaystyle {\phi }_n}$ means finding a function ${\displaystyle {\mathrm{\Phi }}_n}$, such that for any program input ${\displaystyle x}$, the complexity/cost of computing ${\displaystyle {\phi }_n}$ on that input is ${\displaystyle {\mathrm{\Phi }}_n(x)}$. If program ${\displaystyle {\phi }_n}$ does not halt on ${\displaystyle x}$, then ${\displaystyle {\mathrm{\Phi }}_n(x)}$ should be undefined. Otherwise, ${\displaystyle {\mathrm{\Phi }}_n(x)}$ should be a definite natural number. This gives us the first axiom:

• The domains of ${\displaystyle {\phi }_i}$ and ${\displaystyle {\mathrm{\Phi }}_i}$ are identical.

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

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

These are the Blum axioms. A Blum complexity measure is a pairing ${\displaystyle (\phi ,\mathrm{\Phi })}$ that satisfies the Blum axioms.

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

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

Examples

Time complexity is a Blum complexity measure. To decide whether ${\displaystyle {\mathrm{\Phi }}_i(x)\le c}$, simulate ${\displaystyle {\phi }_i(x)}$ for ${\displaystyle c}$ steps. If the machine halts before ${\displaystyle c}$ steps are done, then output TRUE, else output FALSE.

Similarly, space complexity (or any computable combination of time and space), is a Blum complexity measure.

${\displaystyle (\phi ,\phi )}$ is not a complexity measure, since it fails the second axiom.