 Blum axioms

In computational complexity theory the Blum axioms or Blum complexity axioms are axioms which 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 wellknown measures satisfying these axioms are those of time (i.e., running time) and space (i.e., memory usage).
Contents
Definitions
A Blum complexity measure is a tuple (φ,Φ) with φ a Gödel numbering of the partial computable functions and a computable function
which satisfies the following Blum axioms. We write φ_{i} for the ith partial computable function under the Gödel numbering φ, and Φ_{i} for the partial computable function Φ(i).
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.
Notes
A Blum complexity measure is defined using computable functions without any reference to a specific model of computation. In order to make the definition more accessible we rephrase the Blum axioms in terms of Turing machines:
A Blum complexity measure is a function Φ from pairs (Turing machine M, input x to M) to the natural numbers union infinity. Furthermore, Φ should satisfy the following axioms:
 Φ(M,x) is finite if and only if M(x) halts
 There is an algorithm which, on input (M,x,n) decides if Φ(M,x) = n
For example, suppose Φ(M,x) gives the number of time steps that the machine M runs for on input x before halting. The first axiom is clear; the second follows because a universal Turing machine can simulate M on x while counting its steps. If M exceeds n steps, it can halt and reject, so there is no need to determine if M halts on x.
Complexity classes
For a total computable function f complexity classes of computable functions can be defined as
C(f) is the set of all computable functions with a complexity less than f. C^{0}(f) is the set of all booleanvalued functions with a complexity less than f. If we consider those functions as indicator functions on sets, C^{0}(f) can be thought of as a complexity class of sets.
References
 M. Blum. "A machineindependent theory of the complexity of recursive functions". Journal of the ACM, 14(2):322 336, 1967.
Categories: Structural complexity theory
 Mathematical axioms
Wikimedia Foundation. 2010.
Look at other dictionaries:
Blum — Blume means flower in German. In English, the name Blum can either be pronounced /blʌm/, /blu:m/ or /blum/.People*Brad Blum CEO of Burger King from 2002 until 2004. *Geoff Blum baseball player *H Steven Blum three star general of the United… … Wikipedia
Manuel Blum — Born April 26, 1938 (1938 04 26) (age 73) Caracas, Venezuela Residence Pittsburgh … Wikipedia
Kolmogorov complexity — In algorithmic information theory (a subfield of computer science), the Kolmogorov complexity of an object, such as a piece of text, is a measure of the computational resources needed to specify the object. It is named after Soviet Russian… … Wikipedia
List of mathematics articles (B) — NOTOC B B spline B* algebra B* search algorithm B,C,K,W system BA model Ba space Babuška Lax Milgram theorem Baby Monster group Baby step giant step Babylonian mathematics Babylonian numerals Bach tensor Bach s algorithm Bachmann–Howard ordinal… … Wikipedia
Algorithmic information theory — is a subfield of information theory and computer science that concerns itself with the relationship between computation and information. According to Gregory Chaitin, it is the result of putting Shannon s information theory and Turing s… … Wikipedia
Complexity — For other uses, see Complexity (disambiguation). In general usage, complexity tends to be used to characterize something with many parts in intricate arrangement. The study of these complex linkages is the main goal of complex systems theory. In… … Wikipedia
Complexity class — In computational complexity theory, a complexity class is a set of problems of related resource based complexity. A typical complexity class has a definition of the form: the set of problems that can be solved by an abstract machine M using… … Wikipedia
Computable function — Total recursive function redirects here. For other uses of the term recursive function , see Recursive function (disambiguation). Computable functions are the basic objects of study in computability theory. Computable functions are the formalized … Wikipedia
Computational complexity theory — is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other. In this context, a… … Wikipedia
Europe, history of — Introduction history of European peoples and cultures from prehistoric times to the present. Europe is a more ambiguous term than most geographic expressions. Its etymology is doubtful, as is the physical extent of the area it designates.… … Universalium