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