Blum axioms
In
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, 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).
Definitions
A Blum complexity measure is a pair with a
partial computable functions
and a computable function
which satisfies the following Blum axioms. We write for the i-th
partial computable function
under the Gödel numbering , and for the partial computable function .
Examples
- is a complexity measure, if is either the time or the memory (or some suitable combination thereof) required for the computation coded by i.
- is not a complexity measure, since it fails the second axiom.
Complexity classes
For a
total computable function
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 . If we consider those functions as indicator functions on sets, can be thought of as a complexity class of sets.
References
- S2CID 15710280.