ギャップ定理

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