查看“︁布盧姆加速定理”︁的源代码

{{NoteTA|G1=IT}}

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

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

== 定理敍述 ==

給定[[布盧姆公理|布盧姆複雜度衡量]]<math>(\varphi, \Phi)</math>和二元[[可計算函數|全可計算函數]]<math>f</math>，必有全可計算謂詞<math>g</math>（即輸出只能為[[布林_(資料類型)|布爾值]]<math>0, 1</math>的全可計算函數），使得對於<math>g</math>的每個程式<math>i</math>，都有<math>g</math>的另一個程式<math>j</math>，使得對[[幾乎所有]]輸入<math>x</math>，都有
:<math>f(x, \Phi_j(x)) \leq \Phi_i(x). </math>

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

== 參見 ==
* {{le|哥德爾加速定理|Gödel's speed-up theorem}}

== 參考資料 ==
* {{Cite journal | last = Blum | first = Manuel | authorlink = 曼纽尔·布卢姆 | title = A Machine-Independent Theory of the Complexity of Recursive Functions | doi = 10.1145/321386.321395 | journal = [[ACM期刊|Journal of the ACM]] | volume = 14 | issue = 2 | pages = 322–336 | year = 1967 | url = http://port70.net/~nsz/articles/classic/blum_complexity_1976.pdf | access-date = 2021-08-09 | archive-date = 2016-01-15 | archive-url = https://web.archive.org/web/20160115171146/http://port70.net/~nsz/articles/classic/blum_complexity_1976.pdf | dead-url = no }}
* {{Cite journal | last = Van Emde Boas | first = Peter 
  | title = Ten years of speedup | doi = 10.1007/3-540-07389-2_179
 | periodical = Proceedings of Mathematical Foundations of Computer Science, 4th Symposium, Mariánské Lázně, September 1-5, 1975 | editor-first = Jiří | editor-last = Bečvář
 | series = Lecture Notes in Computer Science | volume = 32 | publisher = Springer-Verlag | year = 1975 | pages = 13–29}}.

== 外部鏈結 ==
* {{MathWorld|title=Blum's Speed-Up Theorem|urlname=BlumsSpeed-UpTheorem}}

[[Category:計算複雜性理論]]
[[Category:數學定理]]