布卢姆加速定理
维基百科,自由的 encyclopedia
在计算复杂性理论,布卢姆加速定理(英语:Blum's speedup theorem)为关于可计算函数复杂度的基本定理,最早由曼纽尔·布卢姆在1967年提出。
选定一种编程语言后,每个可计算函数仍由无穷多个程序实现,该些程序可能各有优劣。给定某个可计算函数和复杂度衡量时,算法理论经常查找计算该函数“最不复杂”的算法(称为“最优”,例如当复杂度用时间衡量时,便是“最快”)。布鲁姆加速定理断言,任何复杂度衡量下,都存在某个没有最优算法的可计算函数,亦即,任何该函数的程序实现都会比另一个实现复杂。此结论同时说明,无法同时定义全部可计算函数的复杂度(函数的复杂度是其最优程序的复杂度)。当然,不排除能找到特定函数的最优程序,并计算其复杂度。