Complexity Measure

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). DEFINITIONS A Blum complexity measure is a tuple $(arphi, \Phi)$ with $arphi$ a Gödel Numbering of the Partial Computable Function s $\mathbf{P}^{(1)}$ and a computable function : $\Phi: \mathbb{N} o \mathbf{P}^{(1)}$ which satisfies the following Blum axioms. We write $arphi_i$ for the ''i''-th Partial Computable Function under the Gödel numbering $arphi$ , and $\Phi_i$ for the partial computable function $\Phi(i)$ . the Domain of $arphi_i$ and the domain of $\Phi_i$ is identical.
	:<math>C(f) :	\{ arphi_i \in \mathbf{P}^{(1)} orall x \Phi_i(x) \leq f(x) \}</math>
	:<math>C^0(f) :	\{ h \in C(f) \mathrm{codom}(h) \subseteq \{0,1\} \}</math>

	CATEGORIES ABOUT BLUM AXIOMS

	computational complexity theory

	mathematical axioms

Information About