神託機械の複雑性クラス
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/11/28 15:11 UTC 版)
クラス 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 の証拠とされることもある。だが、ランダムオラクルにとっては真だが、通常のチューリングマシンでは偽となるような文がありうる。
※この「神託機械の複雑性クラス」の解説は、「神託機械」の解説の一部です。
「神託機械の複雑性クラス」を含む「神託機械」の記事については、「神託機械」の概要を参照ください。
- 神託機械の複雑性クラスのページへのリンク
