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

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

${\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]これはギャップ定理が複雑性クラスの不適切な命名によって生じるものであることを示している。