Difference between revisions of "Blum axioms"

From Wiki @ Karl Jones dot com
Jump to: navigation, search
 
Line 1: Line 1:
 
In [[computational complexity theory]] the '''Blum axioms''' or '''Blum complexity axioms''' are [[Axiom|axioms]] that specify desirable properties of complexity measures on the set of [[Computable function|computable functions]].
 
In [[computational complexity theory]] the '''Blum axioms''' or '''Blum complexity axioms''' are [[Axiom|axioms]] that specify desirable properties of complexity measures on the set of [[Computable function|computable functions]].
  
The axioms were first defined by Manuel Blum in 1967.
+
== Description ==
  
Importantly, the [[Speedup theorem|Speedup]] and [[Gap theorem|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).
+
The axioms were first defined by [[Manuel Blum]] in 1967.
 +
 
 +
Importantly, the [[Speedup theorem|Speedup]] and [[Gap theorem|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 ==
 
== See also ==
  
 
* [[Axiom]]
 
* [[Axiom]]
 +
* [[Complexity]]
 +
* [[Complexity class]]
 
* [[Computable function]]
 
* [[Computable function]]
 
* [[Computational complexity theory]]
 
* [[Computational complexity theory]]
Line 16: Line 22:
 
* [https://en.wikipedia.org/wiki/Blum_axioms Blum axioms] @ Wikipedia
 
* [https://en.wikipedia.org/wiki/Blum_axioms Blum axioms] @ Wikipedia
  
 +
[[Category:Complexity]]
 
[[Category:Computation]]
 
[[Category:Computation]]
 
[[Category:Mathematics]]
 
[[Category:Mathematics]]

Latest revision as of 05:27, 5 May 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.

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

External links