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

, Blum's speedup theorem, first stated 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, is a fundamental theorem about the complexity 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. Each computable function has an infinite number of different program representations in a given programming language. In the theory of

algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...

s one often strives to find a program with the smallest complexity for a given computable function and a given complexity measure (such a program could be called ''optimal''). Blum's speedup theorem shows that for any complexity measure, there exists a computable function, such that there is no optimal program computing it, because every program has a program of lower complexity. This also rules out the idea there is a way to assign to arbitrary functions ''their'' computational complexity, meaning the assignment to any ''f'' of the complexity of an optimal program for ''f''. This does of course not exclude the possibility of finding the complexity of an optimal program for certain specific functions.

Speedup theorem

Given a

Blum complexity measure 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 ...

(\varphi, \Phi)

and a total computable function

f

with two parameters, then there exists a total

computable predicate 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 ...

g

(a boolean valued computable function) so that for every program

i

for

g

, there exists a program

j

for

g

so that for

almost all In mathematics, the term "almost all" means "all but a negligible amount". More precisely, if X is a set, "almost all elements of X" means "all elements of X but those in a negligible subset of X". The meaning of "negligible" depends on the math ...

x

f(x, \Phi_j(x)) \leq \Phi_i(x) \,

f

is called the speedup function. The fact that it may be as fast-growing as desired (as long as it is computable) means that the phenomenon of always having a program of smaller complexity remains even if by "smaller" we mean "significantly smaller" (for instance, quadratically smaller, exponentially smaller).

References

* * .

External links

* {{MathWorld, title=Blum's Speed-Up Theorem, urlname=BlumsSpeed-UpTheorem Theorems in computational complexity theory

Speedup theorem

See also

References

External links