神託機械
神託機械は、例えばオラクル A について P と NP の関係を考えることでP≠NP予想の研究に役立つ。例えば、P=NP かつ P≠NP であるような言語 A と B が存在することが示されている(Baker、Gill、Solovay、1975)。どのような相対化された証明方法(すなわち、オラクルの有無が影響しない方法)もP=NP問題に答えられないことから、P=NP問題が両方の方法を相対化するという事実はこの問題が難しいということの証拠である。
考えられる様々な神託機械から無作為の1つの神託機械を選ぶ場合を考える。神託機械 A が無作為に選ばれた場合、確率 1 で P≠NP となる(Bennett, Gill, 1981)。ある質問がほとんど全ての神託機械で真となる場合、「ランダムオラクル」についても真と言える。これは、P≠NP の証拠とされることもある。だが、ランダムオラクルにとっては真だが、通常のチューリングマシンでは偽となるような文がありうる。