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

ギャップ定理（ギャップていり、英: Gap theorem）またはボロディン-トラクテンブロートのギャップ定理は計算可能関数の複雑性に関する重要な定理である。^[1]

これは本質的にはいくらでも大きな計算可能なギャップが複雑性クラスの階層に存在することを示している。計算資源の増加を表現する任意の計算可能関数 ${\displaystyle F}$ に対して、関数 ${\displaystyle t}$ を求めて、${\displaystyle t}$-制限計算可能な関数の集合と ${\displaystyle Ft}$-制限計算可能関数の集合が一致するようにできる。

この定理はボリス・トラクテンブロート（英語版）^[2]とアラン・ボロディン（英語版）^[3][4]によって独立に示された。

この定理の一般的な形は次のようである：

${\displaystyle \Phi }$ を 抽象（ブラム）複雑性測度とする。任意の全域計算可能関数 ${\displaystyle g}$ で ${\displaystyle g(x)\geq x}$ なるものに対して、強単調な全域計算可能関数 ${\displaystyle t}$ が存在して、${\displaystyle t}$ と ${\displaystyle g\circ t}$ を制限とする複雑性クラスが同値となる。

この定理は具体的な計算模型について言及することなくブラムの公理だけを用いて証明できる。したがって定理は時間、空間、または他の妥当なあらゆる複雑性の尺度に対して適用できる。

特別な場合として時間複雑性に適用すれば、これはもっと単純に次のように述べられる：

任意の全域計算可能関数 ${\displaystyle g:\mathbb {N} \to \mathbb {N} }$ で ${\displaystyle g(x)\geq x}$ なるものに対して、強単調な時間限定 ${\displaystyle T(n)}$ が存在して ${\displaystyle DTIME(g(T(n)))=DTIME(T(n))}$ が成り立つ。

限定関数 ${\displaystyle T(n)}$（そしてその計算量）は非常に大きい（さらには構成不可能（英語版）となりうる) から、ギャップ定理から ${\displaystyle {\mathcal {P}}}$ や ${\displaystyle {\mathcal {NP}}}$ のような低い計算量クラスについて興味のある結果は得られない。またこの定理は時間階層定理（英語版）や空間階層定理（英語版）と矛盾しない。

本来のギャップ定理は上記のものよりも強い次の主張である：

${\displaystyle \Phi }$ を抽象複雑性測度とする。任意の全域計算可能関数 ${\displaystyle g}$ で ${\displaystyle g(x)\geq x}$ なるものに対して、強単調な全域計算可能関数 ${\displaystyle t}$ が存在して、${\displaystyle t}$ と ${\displaystyle g\circ t}$ を制限とする指標の全体が一致する。

これによれば ${\displaystyle t}$ と ${\displaystyle g\circ t}$ との間の複雑さを持つ指標はそもそも存在しないから、複雑さ ${\displaystyle g\circ t}$ 程度で計算可能な関数で複雑さ ${\displaystyle t}$ 程度でも計算可能なものが存在する、というわけではない。したがってギャップ定理は加速定理ではない。^[5]

複雑性クラスは ${\displaystyle \mathrm {C} (t)}$ と表されるが、名前 ${\displaystyle t}$ には複数の取り方がある。時間階層定理や空間階層定理は、構成可能性という良い性質を持つ関数で名付けられた複雑性クラスは、ある大きさを超えるギャップを持たないことを示している。抽象複雑性においても、正直さ（英: honestness）と呼ばれる良い性質を持つ関数で名付けられた複雑性クラスにはギャップ現象が生じないことが知られている^[6]。この名称は複雑性クラスの実際の計算量を「正直」に表していることによる。正直さは関数の計算複雑性が入力と出力に対して大きすぎないという性質である。McCraightとMeyerは計算可能関数で命名された複雑性クラスは必ず正直な計算可能関数に改名できることを証明した。^[7]これはギャップ定理が複雑性クラスの不適切な命名によって生じるものであることを示している。

${\displaystyle {\mathcal {P}}^{(1)}}$ を計算可能部分関数のクラスとする。写像 ${\displaystyle F:{\mathcal {P}}^{(1)}\to {\mathcal {P}}^{(1)}}$ が実効作用素とは、計算可能全域関数 ${\displaystyle S}$ が存在して ${\displaystyle F\varphi _{e}=\varphi _{S(e)}}$ が成り立つことをいう。ただし ${\displaystyle \varphi _{e}}$ は ${\displaystyle {\mathcal {P}}^{(1)}}$ のゲーデル・ナンバリングである。とくに全域関数を全域関数に写す作用素は全域的であるという。ギャップ定理は全域性を保つ実効的作用素 ${\displaystyle Gf=g\circ f}$ に対して ${\displaystyle t}$ を求めて ${\displaystyle t}$ と ${\displaystyle Gt}$ の間にギャップが存在するようにできるというものである。ロバート・リー・コンスタブル（英語版）はギャップ現象が任意の全域性を保つ実効的作用素に対して成り立つことを示した。^[8]

${\displaystyle \Phi }$ を抽象複雑性測度とする。任意の全域性を保つ実効的作用素 ${\displaystyle F}$ で ${\displaystyle Ff\geq f}$ なるものに対して、強単調な全域計算可能関数 t が存在して、${\displaystyle t}$ と ${\displaystyle Ft}$ を制限とする指標の全体が一致する。

• ブラムの加速定理