布卢姆加速定理

在计算复杂性理论，布卢姆加速定理（英语：Blum's speedup theorem）为关于可计算函数复杂度的基本定理，最早由曼纽尔·布卢姆在1967年提出。

选定一种编程语言后，每个可计算函数仍由无穷多个程序实现，该些程序可能各有优劣。给定某个可计算函数和复杂度衡量时，算法理论经常查找计算该函数“最不复杂”的算法（称为“最优”，例如当复杂度用时间衡量时，便是“最快”）。布鲁姆加速定理断言，任何复杂度衡量下，都存在某个没有最优算法的可计算函数，亦即，任何该函数的程序实现都会比另一个实现复杂。此结论同时说明，无法同时定义全部可计算函数的复杂度（函数的复杂度是其最优程序的复杂度）。当然，不排除能找到特定函数的最优程序，并计算其复杂度。

定理叙述

给定布卢姆复杂度衡量$(\varphi ,\Phi )$和二元全可计算函数$f$，必有全可计算谓词$g$（即输出只能为布尔值$0,1$的全可计算函数），使得对于$g$的每个程序$i$，都有$g$的另一个程序$j$，使得对几乎所有输入$x$，都有

$f(x,\Phi _{j}(x))\leq \Phi _{i}(x).$

粗略而言，上式表明存在程序$j$，使其复杂度$\Phi _{j}(x)$比程序$i$的复杂度$\Phi _{i}(x)$更小，且可以远远更小（“远远”的含义由$f$指定）。$f$称为加速函数，它可以很大（只需可计算）。例如，若取$f(x,y)=2^{y}$，则$j$的复杂度很小，为$O(\log \Phi _{i}(x))$。

参见

• 哥德尔加速定理

参考资料

• 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.