TOPICS
Search

Blum's Speed-Up Theorem

Blum's speed-up theorem states that 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

References

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 Resource. https://mathworld.wolfram.com/BlumsSpeed-UpTheorem.html

Subject classifications