布卢姆加速定理

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

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

定理叙述

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

 

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

参见

参考资料

外部链接