# Blum's speedup theorem

__: Rules out assigning to arbitrary functions their computational complexity__

**Short description**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 representations in a given programming language. In the theory of algorithms 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 [math]\displaystyle{ (\varphi, \Phi) }[/math] and a total computable function [math]\displaystyle{ f }[/math] with two parameters, then there exists a total computable predicate [math]\displaystyle{ g }[/math] (a boolean valued computable function) so that for every program [math]\displaystyle{ i }[/math] for [math]\displaystyle{ g }[/math], there exists a program [math]\displaystyle{ j }[/math] for [math]\displaystyle{ g }[/math] so that for almost all [math]\displaystyle{ x }[/math]

- [math]\displaystyle{ f(x, \Phi_j(x)) \leq \Phi_i(x) \, }[/math]

[math]\displaystyle{ f }[/math] 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).

## See also

## References

- Blum, Manuel (1967). "A Machine-Independent Theory of the Complexity of Recursive Functions".
*Journal of the ACM***14**(2): 322–336. doi:10.1145/321386.321395. http://port70.net/~nsz/articles/classic/blum_complexity_1976.pdf. - Van Emde Boas, Peter (1975). Bečvář, Jiří. ed. "Ten years of speedup".
*Proceedings of Mathematical Foundations of Computer Science, 4th Symposium, Mariánské Lázně, September 1-5, 1975*. Lecture Notes in Computer Science (Springer-Verlag)**32**: 13–29. doi:10.1007/3-540-07389-2_179..

## External links

- Weisstein, Eric W.. "Blum's Speed-Up Theorem". http://mathworld.wolfram.com/BlumsSpeed-UpTheorem.html.

Original source: https://en.wikipedia.org/wiki/Blum's speedup theorem.
Read more |