跳转到内容

布卢姆加速定理

本页使用了标题或全文手工转换
维基百科,自由的百科全书

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

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

定理叙述

给定布卢姆复杂度衡量和二元全可计算函数,必有全可计算谓词(即输出只能为布尔值的全可计算函数),使得对于的每个程序,都有的另一个程序,使得对几乎所有输入,都有

粗略而言,上式表明存在程序,使其复杂度比程序的复杂度更小,且可以远远更小(“远远”的含义由指定)。称为加速函数,它可以很大(只需可计算)。例如,若取,则的复杂度很小,为

参见

参考资料

外部链接