間隙定理 在計算複雜性理論間隙定理又稱鮑羅丁特拉赫堅布羅特間隙定理為與可计算函数複雜度有關的重要定理 定理斷言复杂性类的層階之間有任意大的可計算間隙意思是若給定任意一個可計算函數 g displaystyle g 表示計算資源增加一次的效果則必能找到某個資源上限 T  n  displaystyle Tn 使得即使將資源上限增加一次變成 g  T  n   displaystyle gTn 也無法計算更多函數 定理由鮑里斯特拉赫堅布羅特英语Boris Trakhtenbrot和艾倫鮑羅丁英语Allan Borodin分別獨立證出 雖然特拉赫堅布羅特的推導比鮑羅丁早幾年但時值冷戰該定理直到鮑羅丁發表後才為西方認識