作用素ギャップ定理
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2016/12/14 23:42 UTC 版)
「ギャップ定理 (計算複雑性理論)」の記事における「作用素ギャップ定理」の解説
P ( 1 ) {\displaystyle {\mathcal {P}}^{(1)}} を計算可能部分関数のクラスとする。写像 F : P ( 1 ) → P ( 1 ) {\displaystyle F:{\mathcal {P}}^{(1)}\to {\mathcal {P}}^{(1)}} が実効作用素とは、計算可能全域関数 S {\displaystyle S} が存在して F φ e = φ S ( e ) {\displaystyle F\varphi _{e}=\varphi _{S(e)}} が成り立つことをいう。ただし φ e {\displaystyle \varphi _{e}} は P ( 1 ) {\displaystyle {\mathcal {P}}^{(1)}} のゲーデル・ナンバリングである。とくに全域関数を全域関数に写す作用素は全域的であるという。ギャップ定理は全域性を保つ実効的作用素 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} を制限とする指標の全体が一致する。
※この「作用素ギャップ定理」の解説は、「ギャップ定理 (計算複雑性理論)」の解説の一部です。
「作用素ギャップ定理」を含む「ギャップ定理 (計算複雑性理論)」の記事については、「ギャップ定理 (計算複雑性理論)」の概要を参照ください。
- 作用素ギャップ定理のページへのリンク
