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

ギャップ定理

ギャップ定理（英: Gap theorem）、またはボロディン-トラクテンブロートのギャップ定理は、計算可能関数の複雑性に関する重要な概念です。この定理は、計算可能な関数が無限に多くの複雑性階層を持つことを示しています。つまり、計算資源が増えるにつれて、計算可能な関数の複雑性についても大きなギャップが生じることを意味しています。この特定の性質は、ボリス・トラクテンブロートとアラン・ボロディンによって独立に確立されました。

定理の基本的な理解

ギャップ定理は次のように表現できます。抽象的な複雑性測度を 6丸で表すとします。この時、任意の全域計算可能関数で、入力値に対してその出力が常に入力以上である場合、すなわち g(x) ≥ x が成り立つとします。すると、強単調な全域計算可能関数 t が存在し、t および g∘t を制限した際の複雑性クラスが同じ性質を持つことが示されます。

この定理は、特定の計算モデルを参照することなく、ブラムの公理に基づいて証明されるため、幅広い場面で適用可能です。特に、時間的および空間的複雑性の理論において重要です。

例えば、時間の複雑性における特例として、g: N → N という全域計算可能関数で g(x) ≥ x の場合に、十分に大きな関数 T(n) が存在し、DTIME(g(T(n))) = DTIME(T(n)) が成り立つことが示されます。この結果は、問題の計算量を評価する上で非常に有用です。

ただし、この定理から導かれる g と T の関数に対しては、必ずしも具体的な計算量クラスである P や NP についての結果は得られないことに注意が必要です。

加速定理との関連

元々のギャップ定理は、さらに強力な主張に基づいています。すなわち、抽象複雑性測度 6丸 に対して、上記の条件を満たす任意の全域計算可能関数に対し、強単調な全域計算可能関数 t が存在し、t と g∘t の指標全体が一致するというものです。これにより、g∘t の複雑性と t の間に関係が存在しないことが明らかとなり、この点が加速定理との違いを際立たせます。

honesty定理

複雑性クラスは C(t) により表されますが、ここでの t の解釈はいくつかの方法があります。時間階層定理や空間階層定理が示しているように、特定の良好な性質を持つ複雑性クラスは、ある水準を超えるギャップを持たないことが確立されています。この状態は、正直さ（honesty）として知られ、関数の計算複雑性が入力および出力に対して過剰ではないという特性を示しています。McCraightとMeyerは、計算可能関数で名付けられた複雑性クラスは常に正直な計算可能関数に改名できることを示しました。

作用素ギャップ定理

ある計算可能部分関数のクラス、すなわち {
m P}^{(1)} に対する写像 F が実効作用素である場合、全域的な計算可能関数 S を用いて Fφ_e = φ_S(e) が成立します。この観点から、ギャップ定理は間接的に、全域性を持つ実効的作用素に対しても適用可能であることを示します。

全体として、ギャップ定理は計算可能関数の複雑性における非常に重要な概念であり、計算資源の増加に伴う機能の性質を明らかにします。これにより、理論的な計算能力の限界を探るための基本的なフレームワークが提供されます。

もう一度検索