布盧姆加速定理

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

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

定理敍述

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

 

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

參見

參考資料

外部鏈結