Blum's speedup theorem
From Wikipedia, the free encyclopedia
In computational complexity theory Blum's speedup theorem, first stated by Manuel Blum in 1967, is an important 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 needs to find a program with the smallest complexity for a given computable function and a given complexity measure. Blum's speedup theorem states that for any complexity measure there are computable functions which have no smallest program.
Contents |
[edit] Speedup theorem
Given a Blum complexity measure 
and a total computable function f with two parameters, then there exists a total computable predicate 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 x
f is called the speedup function.
[edit] See also
[edit] References
- M. Blum. "A machine-independent theory of the complexity of recursive functions". Journal of the ACM, 14, 322-336, 1967.
- Peter van Emde Boas, Ten years of speedup, Proceedings of MFCS (Jirí Becvár, ed.), Lecture Notes in Computer Science, vol. 32, Springer, 1975, pp. 13–29.
