ギャップ定理 (計算複雑性理論)
本来のギャップ定理は上記のものよりも強い次の主張である:
Φ {\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} を制限とする指標の全体が一致する。
これによれば t {\displaystyle t} と g ∘ t {\displaystyle g\circ t} との間の複雑さを持つ指標はそもそも存在しないから、複雑さ g ∘ t {\displaystyle g\circ t} 程度で計算可能な関数で複雑さ t {\displaystyle t} 程度でも計算可能なものが存在する、というわけではない。したがってギャップ定理は加速定理ではない。