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 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. Blum's speedup theorem shows that for any complexity measure there are computable functions that are not optimal with respect to that measure. 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 and a total computable function with two parameters, then there exists a total computable predicate so that for every program for, there exists a program for so that for almost all
is called the speedup function. The fact that it may be as fast-growing as desired
means that the phenomenon of always having a program of smaller complexity remains even if by "smaller" we mean "significantly smaller".
