ギャップ定理 (計算複雑性理論)
ギャップ定理（ギャップていり、英: Gap theorem）またはボロディン-トラクテンブロートのギャップ定理は計算可能関数の複雑性に関する重要な定理である。[1]
これは本質的にはいくらでも大きな計算可能なギャップが複雑性クラスの階層に存在することを示している。計算資源の増加を表現する任意の計算可能関数 [math]F[/math] に対して、関数 [math]t[/math] を求めて、[math]t[/math]-制限計算可能な関数の集合と [math]Ft[/math]-制限計算可能関数の集合が一致するようにできる。
この定理はボリス・トラクテンブロート[2]とアラン・ボロディン[3][4]によって独立に示された。
Contents
ギャップ定理
この定理の一般的な形は次のようである：
- [math]\Phi[/math] を 抽象（ブラム）複雑性測度とする。任意の全域計算可能関数 [math]g[/math] で [math]g(x) \geq x[/math] なるものに対して、強単調な全域計算可能関数 [math]t[/math] が存在して、[math]t[/math] と [math]g \circ t[/math] を制限とする複雑性クラスが同値となる。
この定理は具体的な計算模型について言及することなくブラムの公理だけを用いて証明できる。したがって定理は時間、空間、または他の妥当なあらゆる複雑性の尺度に対して適用できる。
特別な場合として時間複雑性に適用すれば、これはもっと単純に次のように述べられる：
- 任意の全域計算可能関数 [math]g:\mathbb{N}\to\mathbb{N}[/math] で [math]g(x) \geq x[/math] なるものに対して、強単調な時間限定 [math]T(n)[/math] が存在して [math]DTIME(g(T(n))) = DTIME(T(n))[/math] が成り立つ。
限定関数 [math]T(n)[/math]（そしてその計算量）は非常に大きい（さらには構成不可能となりうる) から、ギャップ定理から [math]\mathcal{P}[/math] や [math]\mathcal{NP}[/math] のような低い計算量クラスについて興味のある結果は得られない。またこの定理は時間階層定理や空間階層定理と矛盾しない。
加速定理との関係
本来のギャップ定理は上記のものよりも強い次の主張である：
- [math]\Phi[/math] を抽象複雑性測度とする。任意の全域計算可能関数 [math]g[/math] で [math]g(x) \geq x[/math] なるものに対して、強単調な全域計算可能関数 [math]t[/math] が存在して、[math]t[/math] と [math]g \circ t[/math] を制限とする指標の全体が一致する。
これによれば [math]t[/math] と [math]g \circ t[/math] との間の複雑さを持つ指標はそもそも存在しないから、複雑さ [math]g \circ t[/math] 程度で計算可能な関数で複雑さ [math]t[/math] 程度でも計算可能なものが存在する、というわけではない。したがってギャップ定理は加速定理ではない。[5]
誠実性定理
複雑性クラスは [math]\mathrm{C}(t)[/math] と表されるが、名前 [math]t[/math] には複数の取り方がある。時間階層定理や空間階層定理は、構成可能性という良い性質を持つ関数で名付けられた複雑性クラスは、ある大きさを超えるギャップを持たないことを示している。抽象複雑性においても、誠実性（英: honestness）と呼ばれる良い性質を持つ関数で名付けられた複雑性クラスにはギャップ現象が生じないことが知られている。[6]誠実性はその関数の計算複雑性が入力と出力に対して大きすぎないという性質である。McCraightとMeyerは計算可能関数で命名された複雑性クラスは誠実な関数に改名できることを証明した。[7]これはギャップ定理が複雑性クラスの命名によって生じるものであることを示している。
作用素ギャップ定理
[math]\mathcal{P}^{(1)}[/math] を計算可能部分関数のクラスとする。写像 [math]F:\mathcal{P}^{(1)}\to \mathcal{P}^{(1)}[/math] が実効作用素とは、計算可能全域関数 [math]S[/math] が存在して [math]F \varphi_{e} = \varphi_{S(e)}[/math] が成り立つことをいう。ただし [math]\varphi_{e}[/math] は [math]\mathcal{P}^{(1)}[/math] のゲーデル・ナンバリングである。とくに全域関数を全域関数に写す作用素は全域的であるという。ギャップ定理は全域性を保つ実効的作用素 [math]Gf = g \circ f[/math] に対して [math]t[/math] を求めて [math]t[/math] と [math]Gt[/math] の間にギャップが存在するようにできるというものである。ロバート・リー・コンスタブルはギャップ現象が任意の全域性を保つ実効的作用素に対して成り立つことを示した。[8]
- [math]\Phi[/math] を抽象複雑性測度とする。任意の全域性を保つ実効的作用素 [math]F[/math] で [math]Ff \geq f[/math] なるものに対して、強単調な全域計算可能関数 t が存在して、[math]t[/math] と [math]Ft[/math] を制限とする指標の全体が一致する。
関連項目
参考文献
- ↑ Fortnow, Lance; Homer, Steve (June 2003). “A Short History of Computational Complexity”. Bulletin of the European Association for Theoretical Computer Science (80): 95–133
- ↑ Trakhtenbrot, Boris A. (1967). The Complexity of Algorithms and Computations (Lecture Notes). Novosibirsk University.
- ↑ Allan Borodin (1969). “Complexity Classes of Recursive Functions and the Existence of Complexity Gaps”. Proc. of the 1st Annual ACM Symposium on Theory of Computing: 67-78.
- ↑ Borodin, Allan (January 1972). “Computational complexity and the existence of complexity gaps”. Journal of the ACM 19 (1): 158–174. doi:10.1145/321679.321691.
- ↑ Borodin, Allan B. (1969). Computational Complexity and the Existence of Complexity Gaps. Cornell University.
- ↑ R.Moll; A.R.Meyer (1974). “Honest Bounds for Complexity Classes of Recursive Functions”. Journal of Symbolic Logic 39 (1): 127-138.
- ↑ E. M. McCreight; A.R.Meyer (1969). “Classes of computable functions defined by bounds on computation: preliminary report”. Proceedings of the first annual ACM symposium on Theory of computing: 79-88.
- ↑ Robert L. Constable (1969). “The operator gap”. IEEE Conference Record of 10th Annual Symposium on Switching and Automata Theory: 20-26.