In
computational complexity theory
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by ...
the Blum axioms or Blum complexity axioms are
axioms
An axiom, postulate, or assumption is a statement that is taken to be true, to serve as a premise or starting point for further reasoning and arguments. The word comes from the Ancient Greek word (), meaning 'that which is thought worthy or f ...
that specify desirable properties of complexity measures on the set of
computable function
Computable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithms, in the sense that a function is computable if there exists an algorithm that can do ...
s. The axioms were first defined by
Manuel Blum
Manuel Blum (born 26 April 1938) is a Venezuelan-American computer scientist who received the Turing Award in 1995 "In recognition of his contributions to the foundations of computational complexity theory and its application to cryptography and ...
in 1967.
Importantly,
Blum's speedup theorem
In computational complexity theory, Blum's speedup theorem, first stated by Manuel Blum in 1967, is a fundamental theorem about the complexity of computable functions.
Each computable function has an infinite number of different program represen ...
and the
Gap theorem
:''See also Gap theorem (disambiguation) for other gap theorems in mathematics.''
In computational complexity theory, the Gap Theorem, also known as the Borodin–Trakhtenbrot Gap Theorem, is a major theorem about the complexity of computable fun ...
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 pair
with
a
numbering
There are many different numbering schemes for assigning nominal numbers to entities. These generally require an agreed set of rules, or a central coordinator. The schemes can be considered to be examples of a primary key of a database management ...
of the
partial computable function
Computable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithms, in the sense that a function is computable if there exists an algorithm that can do ...
s
and a computable function
:
which satisfies the following Blum axioms. We write
for the ''i''-th
partial computable function
Computable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithms, in the sense that a function is computable if there exists an algorithm that can do ...
under the Gödel numbering
, and
for the partial computable function
.
* the
domains of
and
are identical.
* the set
is
recursive
Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematics ...
.
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.
Complexity classes
For a
total computable function
Computable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithms, in the sense that a function is computable if there exists an algorithm that can do ...
complexity class
In computational complexity theory, a complexity class is a set of computational problems of related resource-based complexity. The two most commonly analyzed resources are time and memory.
In general, a complexity class is defined in terms of ...
es 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 function
A Boolean-valued function (sometimes called a predicate or a proposition) is a function of the type f : X → B, where X is an arbitrary set and where B is a Boolean domain, i.e. a generic two-element set, (for example B = ), whose elements are in ...
s with a complexity less than
. If we consider those functions as
indicator function
In mathematics, an indicator function or a characteristic function of a subset of a set is a function that maps elements of the subset to one, and all other elements to zero. That is, if is a subset of some set , one has \mathbf_(x)=1 if x\i ...
s on sets,
can be thought of as a complexity class of sets.
References
{{Reflist
Structural complexity theory
Mathematical axioms