布卢姆公理维基百科,自由的 encyclopedia 布鲁姆公理(英语:Blum Axioms),或称布鲁姆复杂度公理(英语:Blum Complexity Axioms),是计算复杂性理论中,定义可计算函数的复杂度时,应满足的条件。这些公理最先由曼纽尔·布鲁姆于1967年提出。[1] 重要的是,只要复杂度衡量满足这些公理,布卢姆加速定理和间隙定理就成立。满足这些公理的复杂度衡量里,最有名的是有关时间(见时间复杂度)和空间(见空间复杂度)的复杂度。
布鲁姆公理(英语:Blum Axioms),或称布鲁姆复杂度公理(英语:Blum Complexity Axioms),是计算复杂性理论中,定义可计算函数的复杂度时,应满足的条件。这些公理最先由曼纽尔·布鲁姆于1967年提出。[1] 重要的是,只要复杂度衡量满足这些公理,布卢姆加速定理和间隙定理就成立。满足这些公理的复杂度衡量里,最有名的是有关时间(见时间复杂度)和空间(见空间复杂度)的复杂度。