オラクルマシン

計算複雑性理論および計算可能性理論において、オラクルマシンとは、オラクルと呼ばれるブラックボックスに問い合わせることができる抽象的なマシンであり、特定の問題のあらゆるインスタンスに対して解答を与えることができる。${\displaystyle R}$単一の操作で。問題は${\displaystyle R}$⁠は任意の複雑性クラスを持つことができ、停止問題のような決定不能問題である可能性さえあります。別の問題が⁠${\displaystyle R'}$はに還元できる​${\displaystyle R}$多項式時間で、オラクルマシン（${\displaystyle R}$⁠ -oracle) は解決できます⁠${\displaystyle R'}$多項式時間で、次のように言える。${\displaystyle R'}$相対化複雑性クラス に属する$\displaystyle {\mathsf {P}}^{R}}$⁠ .その他の相対化された複雑性クラス、例えば⁠$\displaystyle {\mathsf {NP}}^{R}}$も同様に定義できる。 ^{[ 1 ]}

オラクルマシンは、チューリングマシンとオラクルが接続されたものと考えることができます。この文脈におけるオラクルとは、例えば決定問題や関数問題など、何らかの問題を解決できる実体です。問題は計算可能である必要はなく、オラクルはチューリングマシンやコンピュータプログラムである必要もありません。オラクルは、与えられた計算問題のあらゆるインスタンスに対して解を生成できる、単なる「ブラックボックス」です。

• 決定問題は、自然数（または文字列）の集合Aとして表されます。問題のインスタンスは、任意の自然数（または文字列）です。インスタンスの解は、その数（文字列）が集合に含まれている場合は「YES」、含まれていない場合は「NO」となります。
• 関数問題は、自然数（または文字列）と自然数（または文字列）を関連付ける二項関係Rによって表されます。問題のインスタンスは、Rに対する入力xです。解は、 Rによってxに関連付けられた値です。

オラクルマシンは、チューリングマシンの通常の操作をすべて実行できるだけでなく、オラクルに問い合わせて、そのオラクルにとっての計算問題の任意のインスタンスに対する解を取得することもできます。たとえば、問題が自然数の集合Aの決定問題である場合、オラクルマシンはオラクルに自然数を提供し、オラクルはその数がAの要素であるかどうかを「はい」または「いいえ」で応答します。

オラクルチューリングマシンには、以下で説明するように、多くの同等の定義があります。ここで紹介するのは、van Melkebeek (2003 、p. 43)によるものです。 

オラクルマシンは、チューリングマシンと同様に、以下の要素を含みます。

• 作業テープ：開始も終了もない一連のセルで、各セルにはB（空白を表す）またはテープアルファベットの記号が含まれる。
• 読み書きヘッドは、作業テープの単一セル上に載置され、そのセル内のデータを読み取ったり、新しいデータを書き込んだり、テープ上の位置を増減させたりすることができる。
• 有限個の状態のいずれかを取り得る制御機構であり、現在の状態と読み取られるデータに応じて、さまざまな動作（データの読み取り、データの書き込み、読み書きヘッドの移動、状態の変更など）を実行する。

これらの構成要素に加えて、Oracleマシンには以下のものも含まれます。

• オラクルテープとは、作業テープとは別の、半無限長のテープのことです。オラクルテープのアルファベットは、作業テープのアルファベットとは異なる場合があります。
• 読み書きヘッドと同様に、オラクルテープに沿って左右に移動してシンボルを読み書きできるオラクルヘッド。
• 2つの特別な状態：ASK状態とRESPONSE状態。

オラクルマシンは時折、ASK状態に入ることがあります。この場合、以下の処理が単一の計算ステップで実行されます。

• オラクルテープの内容は、オラクルの計算問題の一例として捉えられる。
• オラクルが参照され、オラクルテープの内容がその問題のインスタンスに対する解決策に置き換えられる。
• オラクルヘッドはオラクルテープ上の最初のマス目に移動します。
• オラクルマシンの状態がRESPONSEに変更されました。

したがって、ASK状態に移行することで、問題インスタンスに対する解決策を単一のステップで取得し、それをオラクルテープに書き込むことができる。

言語Lのオラクルを持つクラスAのアルゴリズムで解ける決定問題の複雑性クラスをA ^Lと呼びます。たとえば、^{PSAT は、}ブール充足可能性問題のオラクルを持つ決定性チューリングマシンで多項式時間で解ける問題のクラスです。表記 A ^Bは、次の定義を使用することで、言語の集合B (または複雑性クラスB )に拡張できます。

${\displaystyle A^{B}=\bigcup _{L\in B}A^{L}}$

あるクラスBに対して言語Lが完全である場合、クラスBの完全性定義で使用される還元をAのマシンが実行できるならば^、AL = ABが^成り立つ。特に、SAT は多項式時間還元に関してNP 完全であるため、 ^PSAT = ^NPとなる。ただし、A = DLOGTIMEの場合、ASAT^はNP^と等しくない可能性がある。（定義は、${\displaystyle A^{B}}$上記の方法は完全に標準的ではありません。時間階層定理や空間階層定理の証明など、いくつかの文脈では、抽象マシン定義クラスが${\displaystyle A}$1つの言語に対して1つのオラクルにしかアクセスできません。この文脈では、${\displaystyle A^{B}}$複雑性クラスが定義されていない場合は、${\displaystyle B}$利用可能な削減に関して完全な問題はない${\displaystyle A}$）

NP ⊆ P ^NPであることは理解されているが、NP ^NP、P ^NP 、NP、P が等しいかどうかという問題は、せいぜい暫定的なものにとどまる。これらは異なると考えられており、これが多項式階層の定義につながる。

オラクルマシンは、オラクルAに対する P ^AとNP ^Aの関係を考慮することで、複雑性クラス P と NP の関係を調査するのに役立ちます。特に、 P A = NP ^{Aかつ P B} ≠ NP ^Bとなる言語AとBが存在することが示されています。^{[ 5 ]} P = NP 問題が両方向に相対化されるという事実は、この質問に答えることが難しい証拠とみなされています。なぜなら、相対化する（つまり、オラクルの追加によって影響を受けない）証明手法は、P = NP^問題に答えることができないからです。^{[ 6 ]}ほとんどの証明手法は相対化します。^{[ 7 ]}

考えられるオラクル（無限集合）の中からランダムにオラクルを選択する場合を考えてみましょう。この場合、確率 1 で P ^A ≠ NP ^Aであることが示されています。^{[ 8 ]}質問がほとんどすべてのオラクルで真である場合、それはランダムオラクルで真であると言われます。この用語の選択は、ランダムオラクルが確率 0 または 1 でのみステートメントを支持するという事実によって正当化されます。（これはコルモゴロフのゼロイチ法則から導かれます。）これは P ≠ NP の弱い証拠にすぎません。なぜなら、ステートメントはランダムオラクルでは真であっても、通常のチューリングマシンでは偽となる可能性があるからです。たとえば、ランダムオラクルAでは IP ^A ≠ PSPACE ^Aですが、IP = PSPACE です。^{[ 9 ]}

停止問題に対するオラクルを備えたマシンは、特定のチューリングマシンが特定の入力で停止するかどうかを判定できますが、一般的には、自身と同じようなオラクルマシン（つまり、停止問題に対するオラクルを備えたマシン）が停止するかどうかを判定することはできません。これにより、より強力な停止オラクルとさらに難しい停止問題を持つマシンの階層が生まれます。このマシンの階層は、算術階層を定義するために使用できます。^{[ 10 ]}

暗号理論において、オラクルはハッシュ関数を用いる暗号プロトコルの安全性を論証するために用いられる。ハッシュ関数の代わりにランダムオラクルが各クエリにランダムかつ一貫性をもって応答する場合、プロトコルの安全性の還元（安全性の証明）が与えられる。ハッシュ関数と同様に、オラクルは攻撃者を含むすべての関係者が利用できるものと仮定される。このような証明は、攻撃者が安全性還元の中核となる難問を解決しない限り、プロトコルを破るためにはハッシュ関数の何らかの興味深い特性を利用しなければならないこと、つまりハッシュ関数をブラックボックス（すなわちランダムオラクル）として扱うことはできないことを示している。