Blum's Speed-Up Theorem

There exists a total computable predicate P such that for any algorithm computing P(x) with running time T(x), there exists another algorithm computing P(x) with computation time O(lnT(x)).

This means that there is no algorithm for the predicate P that is even nearly optimal.

See also

Computation Time

Explore with Wolfram|Alpha


More things to try:


Blum, M. "A Machine-Independent Theory of the Complexity of Recursive Functions." J. ACM 14, 322-336, 1967.Seiferas, J. I. and Meyer, A. R. "Characterization of Realizable Space Complexities." Ann. Pure Appl. Logic 73, 171-190, 1995.

Referenced on Wolfram|Alpha

Blum's Speed-Up Theorem

Cite this as:

Weisstein, Eric W. "Blum's Speed-Up Theorem." From MathWorld--A Wolfram Web Resource.

Subject classifications