ギャップ定理 (計算複雑性理論)
ギャップ定理（ギャップていり、）またはボロディン-トラクテンブロートのギャップ定理は計算可能関数の複雑性に関する重要な定理である。
これは本質的にはいくらでも大きな計算可能なギャップが複雑性クラスの階層に存在することを示している。計算資源の増加を表現する任意の計算可能関数 formula_1 に対して、関数 formula_2 を求めて、formula_2-制限計算可能な関数の集合と formula_4-制限計算可能関数の集合が一致するようにできる。
この定理はとによって独立に示された。