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.
[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).
a numbering of the partial computable functions
and a computable function which satisfies the following Blum axioms.
for the i-th partial computable function under the Gödel numbering
complexity classes of computable functions can be defined as
is the set of all computable functions with a complexity less than
is the set of all boolean-valued functions with a complexity less than
can be thought of as a complexity class of sets.