Blum axioms

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, Blum's speedup theorem and the Gap theorem 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).

A Blum complexity measure is a pair 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 .

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:

This page was last edited on 19 April 2018, at 06:44 (UTC).
Reference: https://en.wikipedia.org/wiki/Blum_axioms under CC BY-SA license.

Related Topics


Warning: DOMDocument::loadHTML(): Tag math invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag semantics invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mrow invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mstyle invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mo invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mi invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mo invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mi invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mo invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag annotation invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag math invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag semantics invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mrow invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mstyle invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mi invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag annotation invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag math invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag semantics invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mrow invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mstyle invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag msup invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mrow invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mi invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mrow invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mo invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mn invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mo invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag annotation invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag math invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag semantics invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mrow invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mstyle invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag msub invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mi invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mrow invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mi invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag annotation invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag math invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag semantics invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mrow invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mstyle invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mi invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag annotation invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag math invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag semantics invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mrow invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mstyle invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag msub invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mi invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mrow invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mi invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag annotation invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag math invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag semantics invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mrow invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mstyle invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mi invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mo invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mi invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mo invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag annotation invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag math invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag semantics invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mrow invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mstyle invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mi invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag annotation invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag math invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag semantics invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mrow invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mstyle invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mi invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag annotation invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag math invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag semantics invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mrow invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mstyle invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mi invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag annotation invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag math invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag semantics invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mrow invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mstyle invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mi invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag annotation invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag math invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag semantics invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mrow invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mstyle invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mi invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag annotation invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Recently Viewed