ギャップ定理 (計算複雑性理論)
この定理の一般的な形は次のようである:
Φ {\displaystyle \Phi } を 抽象(ブラム)複雑性測度とする。任意の全域計算可能関数 g {\displaystyle g} で g ( x ) ≥ x {\displaystyle g(x)\geq x} なるものに対して、強単調な全域計算可能関数 t {\displaystyle t} が存在して、 t {\displaystyle t} と g ∘ t {\displaystyle g\circ t} を制限とする複雑性クラスが同値となる。
この定理は具体的な計算模型について言及することなくブラムの公理だけを用いて証明できる。したがって定理は時間、空間、または他の妥当なあらゆる複雑性の尺度に対して適用できる。
特別な場合として時間複雑性に適用すれば、これはもっと単純に次のように述べられる: