間隙定理維基百科,自由的 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]分別獨立證出。 雖然特拉赫堅布羅特的推導比鮑羅丁早幾年,但時值冷戰,該定理直到鮑羅丁發表後才為西方認識。