ギャップ定理 (計算複雑性理論)
任意の全域計算可能関数 g : N → N {\displaystyle g:\mathbb {N} \to \mathbb {N} } で g ( x ) ≥ x {\displaystyle g(x)\geq x} なるものに対して、強単調な時間限定 T ( n ) {\displaystyle T(n)} が存在して D T I M E ( g ( T ( n ) ) ) = D T I M E ( T ( n ) ) {\displaystyle DTIME(g(T(n)))=DTIME(T(n))} が成り立つ。
限定関数 T ( n ) {\displaystyle T(n)} (そしてその計算量)は非常に大きい(さらには構成不可能(英語版)となりうる) から、ギャップ定理から P {\displaystyle {\mathcal {P}}} や N P {\displaystyle {\mathcal {NP}}} のような低い計算量クラスについて興味のある結果は得られない。またこの定理は時間階層定理(英語版)や空間階層定理(英語版)と矛盾しない。
ギャップ定理は全域性を保つ実効的作用素 G f = g ∘ f {\displaystyle Gf=g\circ f} に対して t {\displaystyle t} を求めて t {\displaystyle t} と G t {\displaystyle Gt} の間にギャップが存在するようにできるというものである。ロバート・リー・コンスタブル(英語版)はギャップ現象が任意の全域性を保つ実効的作用素に対して成り立つことを示した。
Φ {\displaystyle \Phi } を抽象複雑性測度とする。任意の全域性を保つ実効的作用素 F {\displaystyle F} で F f ≥ f {\displaystyle Ff\geq f} なるものに対して、強単調な全域計算可能関数 t が存在して、 t {\displaystyle t} と F t {\displaystyle Ft} を制限とする指標の全体が一致する。