布盧姆加速定理

在計算複雜性理論，布盧姆加速定理（英語：Blum's speedup theorem）為關於可计算函数複雜度的基本定理，最早由曼纽尔·布卢姆在1967年提出。

選定一種編程語言後，每個可計算函數仍由無窮多個程式實現，該些程式可能各有優劣。給定某個可計算函數和複雜度衡量時，算法理論經常尋找計算該函數「最不複雜」的算法（稱為「最優」，例如當複雜度用時間衡量時，便是「最快」）。布魯姆加速定理斷言，任何複雜度衡量下，都存在某個没有最優算法的可計算函數，亦即，任何該函數的程式實現都會比另一個實現複雜。此結論同時說明，無法同時定義全部可計算函數的複雜度（函數的複雜度是其最優程式的複雜度）。當然，不排除能找到特定函數的最優程式，並計算其複雜度。

定理敍述

給定布盧姆複雜度衡量${\displaystyle (\varphi ,\Phi )}$ 和二元全可計算函數${\displaystyle f}$ ，必有全可計算謂詞${\displaystyle g}$ （即輸出只能為布爾值${\displaystyle 0,1}$ 的全可計算函數），使得對於${\displaystyle g}$ 的每個程式${\displaystyle i}$ ，都有${\displaystyle g}$ 的另一個程式${\displaystyle j}$ ，使得對幾乎所有輸入${\displaystyle x}$ ，都有

${\displaystyle f(x,\Phi _{j}(x))\leq \Phi _{i}(x).}$ 

粗略而言，上式表明存在程式${\displaystyle j}$ ，使其複雜度${\displaystyle \Phi _{j}(x)}$ 比程式${\displaystyle i}$ 的複雜度${\displaystyle \Phi _{i}(x)}$ 更小，且可以遠遠更小（「遠遠」的含義由${\displaystyle f}$ 指定）。${\displaystyle f}$ 稱為加速函數，它可以很大（只需可計算）。例如，若取${\displaystyle f(x,y)=2^{y}}$ ，則${\displaystyle j}$ 的複雜度很小，為${\displaystyle O(\log \Phi _{i}(x))}$ 。

參見

• 哥德爾加速定理（英语：Gödel's speed-up theorem）

參考資料

• Blum, Manuel. A Machine-Independent Theory of the Complexity of Recursive Functions (PDF). Journal of the ACM. 1967, 14 (2): 322–336 [2021-08-09]. doi:10.1145/321386.321395. （原始内容 (PDF)于2016-01-15）. 
• Van Emde Boas, Peter. Bečvář, Jiří , 编. Ten years of speedup. Proceedings of Mathematical Foundations of Computer Science, 4th Symposium, Mariánské Lázně, September 1-5, 1975. Lecture Notes in Computer Science (Springer-Verlag). 1975, 32: 13–29. doi:10.1007/3-540-07389-2_179. .

外部鏈結

• 埃里克·韦斯坦因. Blum's Speed-Up Theorem. MathWorld.