Blum axioms  From Wikipedia, the free encyclopedia Jump to:
navigation, search  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, the Speedup and Gap theorems 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 Blum
complexity measure is a tuple (\varphi, \Phi) with \varphi a
Gödel numbering of the partial computable functions
\mathbf{P}^{(1)} and a computable function  \Phi: \mathbb{N} \to
\mathbf{P}^{(1)}  which satisfies the following Blum axioms. We
write \varphi_i for the i-th partial computable function under
the Gödel numbering \varphi, and \Phi_i for the partial
computable function \Phi(i).     • (\varphi, \Phi) is a
complexity measure, if \Phi is either the time or the me