オラクルマシン

ブラックボックスシステム
システム
ブラックボックス、オラクルマシン
方法とテクニック
ブラックボックステスト、ブラックボックス化
関連技術
フィードフォワード、難読化、パターン認識、ホワイトボックス、ホワイトボックステスト、グレーボックステスト、システム識別
基礎
先験情報、制御システム、オープンシステム、オペレーションズリサーチ、熱力学システム
ヴ t e

複雑性理論と計算可能性理論において、オラクルマシンは、決定問題を研究するために使用される抽象マシンです。これは、オラクルと呼ばれるブラックボックスを備えたチューリングマシンとして視覚化でき、単一の操作で特定の問題を解決できます。問題は、任意の複雑性クラスにすることができます。停止問題などの決定不可能な問題も使用できます。

オラクル マシンは、オラクルに接続されたチューリング マシンとして考えることができます。このコンテキストでは、オラクルとは、たとえば決定問題や関数問題などの問題を解決できるエンティティです。問題は計算可能である必要はありません。オラクルはチューリング マシンやコンピュータ プログラムであるとは想定されていません。オラクルは、与えられた計算問題のあらゆるインスタンスに対してソリューションを生成できる 単なる「ブラック ボックス」です。

• 決定問題は、自然数 (または文字列) の集合Aとして表されます。問題のインスタンスは、任意の自然数 (または文字列) です。インスタンスの解決方法は、数値 (文字列) が集合内にある場合は「YES」、そうでない場合は「NO」です。
• 関数問題は、自然数 (または文字列) から自然数 (または文字列) への関数fによって表されます。問題のインスタンスは、fの入力xです。解は値f ( x ) です。

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

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

チューリング マシンのようなオラクル マシンには次のものが含まれます。

• 作業テープ:始まりも終わりもないセルのシーケンス。各セルには B (空白) またはテープ アルファベットの記号が含まれる場合があります。
• 読み取り/書き込みヘッド。作業テープ上の 1 つのセル上にあり、そこにあるデータの読み取り、新しいデータの書き込み、テープ上の位置の増減を行うことができます。
• 制御メカニズム。有限の数の状態のいずれかを取ることができ、現在の状態と読み取られるデータに応じて、さまざまなアクション (データの読み取り、データの書き込み、制御メカニズムの移動、状態の変更) を実行します。

これらのコンポーネントに加えて、オラクル マシンには次のものも含まれます。

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

時々、オラクル マシンは ASK 状態に入ることがあります。その場合、次のアクションが 1 つの計算ステップで実行されます。

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

したがって、ASK 状態に変更すると、オラクル テープに書き込まれた問題インスタンスのソリューションを 1 つのステップで受信できるようになります。

上記で示した定義以外にも、さまざまな定義があります。その多くは、オラクルが意思決定の問題を解決する場合に特化しています。この場合、

• いくつかの定義では、オラクルテープに答えを書き込む代わりに、ASK状態に加えてYESとNOという2つの特別な状態があります。オラクルが参照されると、オラクルテープの内容がオラクルセット内にある場合は次の状態としてYESが選択され、内容がオラクルセット内にない場合はNOが選択されます。^[1]
• いくつかの定義では、個別のオラクル テープは使用されていません。オラクル状態に入ると、テープ シンボルが指定されます。オラクルは、このテープ シンボルが作業テープに出現する回数で照会されます。その回数がオラクル セット内にある場合、次の状態は YES 状態です。そうでない場合、次の状態は NO 状態です。^[2]
• 別の定義では、オラクル テープを読み取り専用にし、ASK 状態と RESPONSE 状態を完全に排除します。マシンを起動する前に、オラクル セットのインジケータ関数が、シンボル 0 と 1 を使用してオラクル テープに書き込まれます。その後、マシンはオラクル テープの正しいマス目をスキャンし、そこにある値を読み取ることで、オラクルに問い合わせることができます。^[3]

これらの定義は、チューリング計算可能性の観点からは同等です。つまり、関数がこれらの定義のいずれかの下で神託計算可能である場合、その関数は、すべての定義の下で特定の神託から神託計算可能です。ただし、計算の複雑さの観点からは、これらの定義は同等ではありません。一般に、独自のアルファベットを持つ可能性のある神託テープを使用する van Melkebeek による定義などが必要です。

言語 L の神託を持つクラス A のアルゴリズムによって解決可能な決定問題の複雑性クラスはA ^Lと呼ばれます。たとえば、 P ^{SAT は、}ブール充足可能性問題に対する神託を持つ決定性チューリングマシンによって多項式時間で解決可能な問題のクラスです。表記 A ^{B は}、次の定義を使用して、言語セット B (または複雑性クラス B) に拡張できます。

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

言語 L が何らかのクラス B に対して完全な場合、A 内のマシンがクラス B の完全性の定義で使用されるリダクションを実行できると仮定すると、 A ^L =A ^{B が}成立します。特に、 SAT は多項式時間リダクションに関してNP 完全であるため、 P ^SAT =P ^NPとなります。ただし、 A = DLOGTIMEの場合、 A ^{SAT はA NP}と等しくない可能性があります。(上記のの定義は完全に標準的ではありません。時間および空間階層定理の証明などの一部のコンテキストでは、抽象マシン定義クラスは 1 つの言語に対して単一のオラクルのみにアクセスできると想定する方が便利です。このコンテキストでは、に使用可能なリダクションに関して複雑性クラスに完全な問題がない場合、 は定義されません。) ${\displaystyle A^{B}}$${\displaystyle A}$${\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が存在することが示されています。^{[4] P = NPの問題が両方向に相対化されるという事実は、この質問に答えるのが難しいことの証拠とみなされます。なぜなら、}相対化する（つまり、オラクルの追加によって影響を受けない）証明手法では、P = NPの質問に答えられないからです。^[5]ほとんどの証明手法は相対化します。^[6]

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

停止問題の神託を持つ機械は、特定のチューリング機械が特定の入力で停止するかどうかを判断できますが、一般的には、それと同等の機械が停止するかどうかを判断することはできません。これにより、より強力な停止神託とさらに困難な停止問題を持つ機械の階層が作成されます。この機械の階層を使用して、算術階層を定義できます。^[9]

暗号学では、ハッシュ関数が使用される暗号プロトコルのセキュリティを論証するためにオラクルが使用されます。ハッシュ関数の代わりにランダムオラクルが各クエリにランダムかつ一貫して回答する場合、プロトコルのセキュリティが低減されます。ハッシュ関数と同様に、オラクルは攻撃者を含むすべての関係者に利用可能であると想定されます。このような証明は、攻撃者がセキュリティ低減の核心にある困難な問題を解決しない限り、プロトコルを破るためにハッシュ関数の興味深い特性を利用する必要があることを示しています。攻撃者はハッシュ関数をブラックボックスとして（つまり、ランダムオラクルとして）扱うことはできません。