10

最近、私はNP問題、計算の複雑さ、理論について研究しています。ついにチューリングマシンの概念を理解できたと思いますが、疑問がいくつかあります。

非決定性チューリングマシンには、読み取られている特定の状態と記号に対して何をするかについていくつかのオプションがあり、ウィキペディアで述べられているように、常に最良のオプションを選択することを受け入れることができます

NTMは、これらのアクションのどれを実行する必要があるかをどのように「認識」しますか？それを見るには2つの方法があります。1つは、このマシンが「最も幸運な推測者」であると言うことです。そのような遷移がある場合、それは常に最終的に受け入れ状態につながる遷移を選択します。もう1つは、マシンが多くのコピーに「分岐」し、それぞれが可能な遷移の1つに従うことを想像することです。DTMにはそれがたどる単一の「計算パス」がありますが、NTMには「計算ツリー」があります。ツリーのいずれかのブランチが「受け入れ」条件で停止した場合、NTMは入力を受け入れたと言います。

私が理解できないのは、これは架空の機械なので、多項式時間でNP問題を解くことができると言うことから何が得られるのでしょうか。つまり、O（1）のNP問題を解決する魔法の機械を理論化することもできますが、それが存在しない可能性がある場合、それから何を得ることができますか？

前もって感謝します。

4

6 に答える 6

15

非決定論的なチューリング マシンは、理解するのが難しい概念です。他の視点を試してみてください:

  1. 最も幸運な推測者である魔法のチューリング マシンを実行する代わりに、パラレル ユニバースでランダムに推測する独立したチューリング マシンを無数に設定する、さらに魔法のメタマシンを実行します。可能なすべての一連の推測は、ある宇宙で行われます。少なくとも 1 つのユニバースでマシンが停止し、入力を受け入れる場合、それで十分です。問題のインスタンスは、これらのパラレル ユニバースを設定したメタマシンによって受け入れられます。すべてのユニバースでマシンが拒否または停止に失敗した場合、メタマシンはインスタンスを拒否します。

  2. あらゆる種類の推測や分岐の代わりに、インスタンスを受け入れる必要があることを別の人に納得させようとしている人を考えてみてください。最初の人は、非決定論的チューリング マシンによって行われる一連の選択肢を提供し、2 人目は、マシンがそれらの選択肢で入力を受け入れるかどうかを確認します。もしそうなら、2番目の人は確信しています。そうでない場合、最初の人は失敗しています (これは、インスタンスが選択の順序で受け入れられないか、最初の人が不適切な順序の選択を選択したためである可能性があります)。

  3. チューリングマシンのことは忘れてください。存在論的二次論理の式で記述できる問題は NP にあります。つまり、平凡な命題論理を採用し、命題変数に対する量指定子を許可し、集合、関係、および関数に対する存在量指定子を最初に追加することを許可します。たとえば、グラフの 3 色可能性は、色 (ノードのセット) に対する存在量化から始まる式で記述できます。

    ∃R∃G∃B

    すべてのノードに色を付ける必要があります。

    ∃ R ∃ G ∃ B (∀ x (R(x) ∨ G(x) ∨ B(x)))

    また、隣接する 2 つのノードが同じ色であってはなりません。エッジ関係を E と呼びます。

    ∃ R ∃ G ∃ B (∀ x (R(x) ∨ G(x) ∨ B(x))) ∧ (∀ x,y ¬ (E(x,y) ∧ ((R(x) ∧ R( y)) ∨ (G(x) ∧ G(y)) ∨ (B(x) ∧ B(y)))))

    2 次変数の存在量化は、完全な推測を行う非決定論的チューリング マシンのようなものです。式 ∃ X (...) が真であることを誰かに納得させたい場合は、X の値を与えることから始めることができます。その多項式時間 NTM とこれらの式は、単に「似ている」だけでなく、実際に等価である Fagin の定理です。記述的複雑さの分野を開始しました: 複雑さのクラスは、チューリング マシンではなく、論理式のクラスによって特徴付けられます。

あなたも言った

O(1) で NP 問題を解決する魔法の機械を理論化することもできます。

はい、できます。これらはオラクル マシン(DBMS とは関係ありません) と呼ばれ、複雑性理論で興味深い結果が得られています。たとえば、ベイカー・ギル・ソロベイの定理では、A にアクセスできるチューリング マシンの場合は P=NP であるが、B にアクセスできるチューリング マシンの場合は P≠NP となるオラクル A と B があると述べています。(A は、非決定論を無関係にする非常に強力なオラクルです。B の定義は少し複雑で、対角化のトリックが含まれます。) これは一種のメタ結果です。P 対 NP の問題を解く証明は、機密でなければなりません。いくつかの種類のオラクルを追加すると失敗するチューリングマシンの定義に十分です。

非決定論的チューリング マシンの価値は、複雑性クラス NP (およびその他) の比較的単純な計算特性を提供することです。計算ツリーまたは 2 次論理式の代わりに、完全な推測ができるように (比較的) わずかに変更されています。

于 2010-10-03T11:06:53.257 に答える
4

そこから得られるのは、多項式時間で NTM によって解決できることを証明することによって、問題が NP にあることを証明できることです。

つまり、NTM を使用して、特定の問題が NP にあるかどうかを調べることができます。

于 2010-09-14T22:15:13.810 に答える
1

定義上、NP はWikipediaで調べることができる非決定論的多項式時間を表します。

次の可能性のある解を無作為に選択して調べる (または組み立てる) 非決定論的チューリング マシンの化身は、多項式時間で NP 問題をある程度の確率で解決します (それが「可能な限り最も幸運であった場合、絶対的な確実性で問題を多項式時間で解決します」)。推測者」）。

したがって、NTMが問題を多項式時間で効果的に解決できるということは、その問題が NP にあることを意味します。これも、問題の NP クラスの定義と同等です。

于 2010-09-14T22:34:41.367 に答える
0

あなたの答えはあなたの質問にあると思います。つまり、与えられた問題を解く NTM を見つけることができれば、それが NP 問題であることを証明できます。

NP 問題は問題の特別なクラスであり、NTM は与えられた問題がそのクラスに属しているかどうかを確認するための単なるツールです。

NTM は特定のマシンではないことに注意してください。NTM は、できることとできないことについて明確に定義されたルールを持つマシンのクラス全体です。「魔法の」マシンを使用するには、それらを定義し、それらが対応する問題の複雑さのクラスを示す必要があります。

詳細については、 http://en.wikipedia.org/wiki/Computational_complexity_theory#Complexity_classes を参照してください。

于 2010-09-14T22:53:59.643 に答える
-1

ヘブライ語ウィキペディアより - 「NTM は主に思考のためのツールであり、そのような機械を実際に実装することは不可能です」. 「NTM」という用語は、「すべてのステップですべての可能なステップを試すアルゴリズム」または「すべてのステップで可能な限り最良の次のステップを選択するアルゴリズム」に置き換えることができます..残りは理解できたと思います. NTM は、そのようなアルゴリズムを視覚化するのに役立つだけです。ここで、視覚化にどのように役立つかを確認できます（Pascal Cuoqの回答で）。

于 2010-09-14T22:24:06.850 に答える
-1

得られるのは、正しいステップを推測する魔法の力があれば、常に正しいことが判明するため、POLYTIME で NPC の問題を解決できるということです。もちろん、常に正しいステップを「推測」できるわけではありません。だから想像です。しかし、虚数が現実世界の問題に適用できるのと同じように、結果は理論的に役立つ場合があります。

元の問題をこのようにモーフィングすることの良い面の 1 つは、さまざまな角度から問題に取り組むことができることです。理論的な領域では、(1) 採用できるアプローチが増える (したがって論文が増える)、(2) 他の分野で表現できる場合は使用できるツールが増えるため、これは良いことです。

于 2010-09-14T22:39:26.840 に答える