Blum's speedup theorem

In <a href="/facts/Computational_complexity_theory/etHuVF3U">computational complexity theory</a>, Blum's speedup theorem, first stated by <a href="/facts/Manuel_Blum/fl3GKhvh">Manuel Blum</a> in 1967, is a fundamental <a href="/facts/Theorem/f2Pe1FMD">theorem</a> about the complexity of <a href="/facts/Computable_function/dzwBlLGn">computable functions</a>.
Each computable function has an infinite number of different program representations in a given <a href="/facts/Programming_language/cWTYbgWa">programming language</a>. In the theory of <a href="/facts/Algorithm/fnl5NmRt">algorithms</a> one often strives to find a program with the smallest complexity for a given computable function and a given <a href="/facts/Computational_complexity_theory/etHuVF3U">complexity measure</a> (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 that 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.

Blum's speedup theorem open-in-new

Blum's speedup theorem