存在一個完全可計算謂詞 
使得對於任何計算 
且執行時間為 
的演算法，都存在另一個計算 
的演算法，其 計算時間 為 
。
這意味著對於謂詞 
，不存在即使是近似最優的演算法。
布盧姆加速定理
參見
計算時間使用 探索
參考文獻
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.在 中被引用
布盧姆加速定理引用此條目為
韋斯stein, Eric W. "布盧姆加速定理。" 來自 Web 資源。 https://mathworld.tw/BlumsSpeed-UpTheorem.html