Blum axioms
From Wiki @ Karl Jones dot com
Revision as of 05:27, 5 May 2016 by Karl Jones (Talk | contribs)
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.
Description
The axioms were first defined by Manuel Blum in 1967.
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).
See also
- Axiom
- Complexity
- Complexity class
- Computable function
- Computational complexity theory
- Computer science
External links
- Blum axioms @ Wikipedia
