Blum axioms

A Blum complexity measure is a pair ${\displaystyle (\varphi ,\Phi )}$ with ${\displaystyle \varphi }$ a numbering of the partial computable functions ${\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 partial computable function 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.

For a total computable function ${\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.