神託機械
神託機械（しんたくきかい、英: oracle machine）または預言機械（よげんきかい）は、計算複雑性理論や計算可能性理論における抽象機械の一種であり、決定問題の研究で使われる。チューリングマシンに神託（oracle）と呼ばれるブラックボックスが付加されたものであり、そのブラックボックスは特定の決定問題を1ステップで決定可能である。チューリングマシンの停止問題のような決定不能な問題にも神託機械を想定することができる。
定義
編集神託機械はオラクル付きのチューリングマシンである。チューリングマシンはオラクルへの入力を自身のテープに書き込み、オラクルにその実行を指示する。1ステップでオラクルはそれを計算し、入力を消去して出力をテープに書き込む。場合によってはチューリングマシンが2本のテープを持つように描かれる場合もあり、一方がオラクルへの入力、もう一方がオラクルからの出力に使われる。
神託機械の複雑性クラス
編集クラス A のアルゴリズムにクラス B の問題を解くオラクルを組み合わせることで解ける決定問題の複雑性クラスを AB と表記する。例えば、決定性チューリングマシンにNPクラスのオラクルが付属したもので多項式時間で解ける問題のクラスは、PNP で表される。このクラスの問題は、NPクラスに多項式時間チューリング還元で還元可能である。
NP ⊆ PNP であることは明らかだが、NPNP、PNP、NP、P の関係（等価かどうか）は未解決の問題である。詳しくは多項式階層を参照されたい。
AB は、クラス A のアルゴリズムに「言語」B のオラクルを付加することで解ける問題のクラスをも意味している。例えば、PSAT は、チューリングマシンに充足可能性問題のオラクルを付与することで多項式時間で解ける問題のクラスである。言語 B がクラス C について完全であるとき、AB=AC が成り立つ。特に SAT はNP完全問題なので、PSAT=PNP となる。
神託機械は、例えばオラクル A について PA と NPA の関係を考えることでP≠NP予想の研究に役立つ。例えば、PA=NPA かつ PB≠NPB であるような言語 A と B が存在することが示されている（Baker、Gill、Solovay、1975）。どのような相対化された証明方法（すなわち、オラクルの有無が影響しない方法）もP=NP問題に答えられないことから、P=NP問題が両方の方法を相対化するという事実はこの問題が難しいということの証拠である。
考えられる様々な神託機械から無作為の1つの神託機械を選ぶ場合を考える。神託機械 A が無作為に選ばれた場合、確率 1 で PA≠NPA となる（Bennett, Gill, 1981）。ある質問がほとんど全ての神託機械で真となる場合、「ランダムオラクル」についても真と言える。これは、P≠NP の証拠とされることもある。だが、ランダムオラクルにとっては真だが、通常のチューリングマシンでは偽となるような文がありうる。
オラクルと停止問題
編集計算不可能とされている計算を行う神託機械を想定することもある。例えばチューリングマシンの停止問題やそれと等価な問題を解ける神託機械である。このようなオラクルを付加された機械をハイパーコンピュータと呼ぶ。
停止問題はそのような機械にも適用される。すなわち、そのような神託機械は、あるチューリングマシンが与えられた入力について停止するかどうかを判定できるが、神託機械自身が与えられた入力について停止するかどうかは判定できない。ここから機械の一種の階層が生み出され、これを算術的階層と呼ぶ。この階層はどこまでいっても判定不能な問題が存在することを示している。
暗号への応用
編集最近の計算機科学での神託機械の応用として、暗号への応用がある。質問に対して無作為だが一貫した答を返す（同じ質問には同じ答を返す）ランダムオラクルがあったとしたとき、非常に安全な一方向性関数として利用できる。すなわちランダムオラクルの出力を得ても、総当り的に入力値を試してみない限り入力を探し出すプログラムは作成できない。これにより非常に強力な暗号ができるが、実際にはランダムオラクルではなく擬似乱数生成器が使われることになる。だが、擬似乱数生成器はランダムオラクルほど安全ではない。
関連項目
編集参考文献
編集- Alan Turing, Systems of logic based on ordinals, Proc. London math. soc., 45, 1939
- C. Papadimitriou. Computational Complexity. Addison-Wesley, 1994. Section 14.3: Oracles, pp. 339 – 343.
- T. P. Baker, J. Gill, R. Solovay. Relativizations of the P =? NP Question. SIAM Journal on Computing, 4(4): 431-442 (1975)
- C. H. Bennett, J. Gill. Relative to a Random Oracle A, PA != NPA != co-NPA with Probability 1. SIAM Journal on Computing, 10(1): 96-113 (1981)
- Michael Sipser (1997年). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X Section 9.2: Relativization, pp.318 – 321.
- Martin Davis, editor: The Undecidable, Basic Papers on Undecidable Propositions, Unsolvable Problems And Computable Functions, Raven Press, New York, 1965. チューリング、ゲーデル、チャーチ、クリーネの論文が掲載されている。