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