私はそれらが現実のものではないことを理解しており、1 つを選択する代わりに 2 つのオプションがある場合は常に計算を分岐しているようです。しかし、たとえば、私がこれを言うなら：
「グラフ G からグラフ H への頂点の全単射 p を非決定論的に推測する」(ここでのコンテキストはグラフ同形性です)
それはどういう意味ですか？私は全単射を理解していますが、「非決定論的推測」と言っています。推測である場合、それはどのようにアルゴリズムのアプローチですか? それが機能することをどのように保証できますか？
そうではなく、ある点を説明しているだけです。基本的に彼らがしていることは、答えを推測し、それが正しいかどうかを (決定論的に) 確認することです。重要なのは答えを推測することではなく、答えが正しいことを確認することです。任意の解が与えられたと言っているようなものです。それは正しいですか? たとえば、計算に指数関数的な時間がかかる問題があり、それらの答えのいくつかは多項式時間でチェックできますが、できないものもあります。したがって、非決定論的 TM が行うことは、迅速にチェックできるものとそうでないものを 2 つに分割することです。そして、これはより大きな問題を提起します。質問の 1 つのグループの解決策を別のグループよりもはるかに迅速に検証できる場合、それらの解決策もより迅速に生成できるでしょうか? この質問はまだ答えられていません。
非決定論的チューリング マシンの物理的な実装は、DNA コンピューターです。たとえば、DNA の巡回セールスマン問題を解決する方法の概要は次のとおりです。
一連の DNA シーケンスを取得/作成します。それぞれの長さはグラフ内のエッジのコストに比例し、エッジが接続する頂点の 1 つを一意に識別するシーケンスを持つスティッキー エンドを持ちます。
大きなビーカーで DNA リガーゼと一緒にそれらを混ぜます。それらは、グラフを通過する可能性のあるすべてのパスを表すシーケンスで互いにアニールします (わかりました、本当に長いものではありません)。
少なくとも 1 つの頂点が欠落しているすべてのシーケンスを削除します。これを行うには、ハイブリダイゼーションを使用して各頂点を順番に選択します。たとえば、「ACGTACA」が頂点 1 をエンコードする場合、「TGTACGA」に結合するシーケンスを選択します。次に、他の頂点ごとにこの選択を繰り返します。
ゲル電気泳動を使用してサイズで残りのシーケンスを並べ替えます。次に、最も短いものを並べます。シーケンスは、グラフを通る最短パスをエンコードします。
イメージする方法はさまざまです。私が便利だと思うのはオラクルモデルです。ファー サイドの漫画で、黒板に「ここで奇跡が起こる」という派生語が中間ステップの 1 つとしてあるのを見たことがありますか? このバージョンの NDTM では、何かを選択する必要がある場合、オラクルが正しいバージョンをテープの右側に書き込みます。(これは、Garey and Johnson, Computers and Intractability から引用したもので、NP 完全問題に関する彼らの古典的な本です。) ただし、正しいものを持っていると仮定することはできません。また、正しいものがない可能性もあります。
したがって、全単射を非決定論的に推測すると、目的に適した全単射が存在する場合、正しい全単射が得られます。
非決定論的チューリング マシンの実装の複雑さは基本的に非決定論的状態では指数関数的であり、非決定論的推測に相当するアルゴリズムは可能なすべての全単射を試すことであるため、これはアルゴリズムの良い基礎ではありません。
理論的な観点から、私はそれを「そのような全単射がある場合....」と翻訳します。アルゴリズムの観点からは、別の本または同じ本の別の章を見つけてください。そのアプローチは、適度に大きなグラフでも役に立たないからです。
私は、「非決定論的に解決策を選択する」ことを意味し、解決策が真であることをテストすると信じています。すべての可能な選択肢 (推測) がテストされるため、ソリューションが保証されます。