Blum axioms

From formulasearchengine
Jump to navigation Jump to search

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.[1]

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).

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 for the i-th partial computable function under the Gödel numbering , and for the partial computable function .

Examples

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 , input for ) to the natural numbers union infinity. Furthermore, should satisfy the following axioms:

For example, suppose 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 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