布盧姆加速定理

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

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

定理敍述

給定布盧姆複雜度衡量和二元全可計算函數,必有全可計算謂詞(即輸出只能為布爾值的全可計算函數),使得對於的每個程式,都有的另一個程式,使得對幾乎所有輸入,都有

粗略而言,上式表明存在程式,使其複雜度比程式的複雜度更小,且可以遠遠更小(「遠遠」的含義由指定)。稱為加速函數,它可以很大(只需可計算)。例如,若取,則的複雜度很小,為

參見

  • 哥德爾加速定理

參考資料

外部鏈結

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.