布卢姆加速定理
在计算复杂性理论,布卢姆加速定理(英语: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..
外部链接
- 埃里克·韦斯坦因. Blum's Speed-Up Theorem. MathWorld.