yawiki.org entry for Blum axioms

	Navigation Home Recent Most Active Popular Blog Credits RSS
	Interaction Register Statistics
	Help Suggestions Contact Us How to Edit Help

[Edit]

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 well-known measures satisfying these axioms are those of time (i.e., running time) and space (i.e., memory usage).

    Blum axioms
        Blum axioms
        Examples
        Complexity classes

top

Blum axioms

A Blum complexity measure is a tuple

(varphi, Phi)

with

varphi

a Gödel numbering of the partial computable functions

mathbf^

and a computable function

$Phi: mathbb o mathbf^$

so that the following Blum axioms are satisfied

for all

i in mathbb

mathrm(varphi_i) = mathrm(Phi_i)

the set

is recursive

top

Examples

(varphi, Phi)

is a complexity measure, if

Phi

is either the time or the memory (or some suitable combination thereof) required for the computation coded by i.

(varphi, varphi)

is not a complexity measure, since it fails the second axiom.

top

Complexity classes

For a total computable function

f

complexity classes of computable functions can be defined as

$C(f)$
=

$C^0(f)$
=

C(f)

is the set of all computable functions with a complexity less than

f

C^0(f)

is the set of all boolean-valued 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.

	Source Privacy License Download Contact Us Atlas Scientus.org Dictionary (Yet Another Wiki) RC : 1.39 MIT OpenCourseWare This article is licensed under the GNU Free Documentation License [copyleft]. It uses material from the Wikipedia article "Blum axioms". link