Difference between revisions of "Blum axioms"
From Wiki @ Karl Jones dot com
Karl Jones (Talk | contribs) (Created page with "In computational complexity theory the '''Blum axioms''' or '''Blum complexity axioms''' are axioms that specify desirable properties of complexity measures on t...") |
Karl Jones (Talk | contribs) |
||
| Line 15: | Line 15: | ||
* [https://en.wikipedia.org/wiki/Blum_axioms Blum axioms] @ Wikipedia | * [https://en.wikipedia.org/wiki/Blum_axioms Blum axioms] @ Wikipedia | ||
| + | |||
| + | [[Category:Computation]] | ||
| + | [[Category:Mathematics]] | ||
Revision as of 18:23, 21 April 2016
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.
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
External links
- Blum axioms @ Wikipedia
