间隙定理维基百科,自由的 encyclopedia 在计算复杂性理论,间隙定理,又称鲍罗丁-特拉赫坚布罗特间隙定理,为与可计算函数复杂度有关的重要定理。[1] 定理断言,复杂性类的层阶之间,有任意大的可计算间隙。意思是,若给定任意一个可计算函数 g {\displaystyle g} ,表示计算资源增加一次的效果,则必能找到某个资源上限 T ( n ) {\displaystyle T(n)} ,使得即使将资源上限增加一次变成 g ( T ( n ) ) {\displaystyle g(T(n))} ,也无法计算更多函数。 定理由鲍里斯·特拉赫坚布罗特(英语:Boris Trakhtenbrot)[2]和艾伦·鲍罗丁(英语:Allan Borodin)[3][4]分别独立证出。 虽然特拉赫坚布罗特的推导比鲍罗丁早几年,但时值冷战,该定理直到鲍罗丁发表后才为西方认识。
在计算复杂性理论,间隙定理,又称鲍罗丁-特拉赫坚布罗特间隙定理,为与可计算函数复杂度有关的重要定理。[1] 定理断言,复杂性类的层阶之间,有任意大的可计算间隙。意思是,若给定任意一个可计算函数 g {\displaystyle g} ,表示计算资源增加一次的效果,则必能找到某个资源上限 T ( n ) {\displaystyle T(n)} ,使得即使将资源上限增加一次变成 g ( T ( n ) ) {\displaystyle g(T(n))} ,也无法计算更多函数。 定理由鲍里斯·特拉赫坚布罗特(英语:Boris Trakhtenbrot)[2]和艾伦·鲍罗丁(英语:Allan Borodin)[3][4]分别独立证出。 虽然特拉赫坚布罗特的推导比鲍罗丁早几年,但时值冷战,该定理直到鲍罗丁发表后才为西方认识。