ギャップ定理 (計算複雑性理論)

ギャップ定理（ギャップていり、）またはボロディン-トラクテンブロートのギャップ定理は計算可能関数の複雑性に関する重要な定理である。
これは本質的にはいくらでも大きな計算可能なギャップが複雑性クラスの階層に存在することを示している。計算資源の増加を表現する任意の計算可能関数 formula_1 に対して、関数 formula_2 を求めて、formula_2-制限計算可能な関数の集合と formula_4-制限計算可能関数の集合が一致するようにできる。
この定理はとによって独立に示された。
ギャップ定理.
この定理の一般的な形は次のようである：
この定理は具体的な計算模型について言及することなくブラムの公理だけを用いて証明できる。したがって定理は時間、空間、または他の妥当なあらゆる複雑性の尺度に対して適用できる。
特別な場合として時間複雑性に適用すれば、これはもっと単純に次のように述べられる：
限定関数 formula_13（そしてその計算量）は非常に大きい（さらにはとなりうる) から、ギャップ定理から formula_16 や formula_17 のような低い計算量クラスについて興味のある結果は得られない。またこの定理はやと矛盾しない。
加速定理との関係.
本来のギャップ定理は上記のものよりも強い次の主張である：
これによれば formula_2 と formula_10 との間の複雑さを持つ指標はそもそも存在しないから、複雑さ formula_10 程度で計算可能な関数で複雑さ formula_2 程度でも計算可能なものが存在する、というわけではない。したがってギャップ定理は加速定理ではない。
誠実性定理.
複雑性クラスは formula_28 と表されるが、名前 formula_2 には複数の取り方がある。時間階層定理や空間階層定理は、構成可能性という良い性質を持つ関数で名付けられた複雑性クラスは、ある大きさを超えるギャップを持たないことを示している。抽象複雑性においても、誠実性（）と呼ばれる良い性質を持つ関数で名付けられた複雑性クラスにはギャップ現象が生じないことが知られている。誠実性はその関数の計算複雑性が入力と出力に対して大きすぎないという性質である。McCraightとMeyerは計算可能関数で命名された複雑性クラスは誠実な関数に改名できることを証明した。これはギャップ定理が複雑性クラスの命名によって生じるものであることを示している。
作用素ギャップ定理.
formula_30 を計算可能部分関数のクラスとする。写像 formula_31 が実効作用素とは、計算可能全域関数 formula_32 が存在して formula_33 が成り立つことをいう。ただし formula_34 は formula_30 のゲーデル・ナンバリングである。とくに全域関数を全域関数に写す作用素は全域的であるという。ギャップ定理は全域性を保つ実効的作用素 formula_36 に対して formula_2 を求めて formula_2 と formula_39 の間にギャップが存在するようにできるというものである。はギャップ現象が任意の全域性を保つ実効的作用素に対して成り立つことを示した。