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

ウィキペディア

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

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/06/02 21:30 UTC 版)

ギャップ定理（ギャップていり、英: Gap theorem）またはボロディン-トラクテンブロートのギャップ定理は計算可能関数の複雑性に関する重要な定理である。^[1]

これは本質的にはいくらでも大きな計算可能なギャップが複雑性クラスの階層に存在することを示している。計算資源の増加を表現する任意の計算可能関数 ${\displaystyle F}$