なぜNPでこの決定不可能な問題がないのですか？

Question

明らかに、NPには管理できない問題はありません。しかし、によれば ウィキペディア:

NPは、回答が「はい」であるインスタンスが、決定論的チューリングマシンによって多項式時間に検証可能な[..証明]を持っているすべての決定問題のセットです。

[...]

問題は、多項式時間に実行される問題の検証剤が存在する場合にのみNPにあると言われます。

次に、次の問題を検討してください。

与えられます ジファンティン方程式, 、整数ソリューションはありますか？

解決策を考えると、それが本当にそれが本当にあることを検証するのは簡単です は 解決策：数値を方程式に差し込むだけです。したがって、問題はNPにあります。でも、 解決 この問題は有名です 管理不可能であることが知られています!

（同様に、停止の問題はNPにあるはずです。なぜなら、「このプログラムがN-Theステップで停止する」という「はい」解像度は、Nステップで検証できるからです。）

明らかに私の理解に何か問題がありますが、それは何ですか？

Answer 1

NPの同等の定義は、それがあるすべての問題で構成されていることです 決定可能 （検証可能ではなく）非決定的なチューリングマシンによる多項式時間で。 NTMSは、NTMSによって決定可能な問題のセットがTMSによって決定可能な問題のセットと同一であるという意味でTMSよりも強力ではないことが知られているため、この定義により、NPには適切な問題はありません。

NPの2つの定義が同等であることを示すために、決定論的検証剤の存在を考えると、非決定論的決定者が存在することを示すことができ、その逆も同様です。

決定論的多項式検証剤があるとします。次に、この問題/検証剤の境界に対応する多項式に対応する多項式に囲まれた長さの証明書を非決定論的に推測し、検証剤を実行するマシンもあります。アルファベットの有限であるため、特定の入力の証明書は有限であり（入力のサイズが多い）、検証剤は多項式時間に実行されます。決定論的）多項式時間。したがって、すべての決定論的検証剤に非決定的な決定者があります。

非決定的な決定者がいる場合は、受け入れるすべての計算について、受領状態に到達するために決定者が取った選択のパスを書き留めることができます。決定者は多項式時間で実行されるため、このパスは最小の多項式の長さになります。そして、決定論的なTMがそのようなパスを検証するのは簡単です は NTMを介して受け入れた状態への有効なパスであるため、そのようなパスは、問題の多項式時間検証の証明書を形成します。したがって、すべての非決定的決定者に決定論的検証剤があります。

したがって、決定不可能な問題 できません 多項式サイズの証明書で動作する検証剤を持っています（そうでなければ、検証剤の存在は決定者の存在を意味します）。

---

停止問題のために検証剤が存在すると主張する場合、あなたが話している証明書は、（TM、I、N）のエンコードであり、TMはnステップで入力Iで停止します。これは実際にnステップで検証できますが、証明書のサイズは、元の問題（停止問題）への（TM、i）入力のサイズの多項式ではありません。 nは任意に大きくなる可能性があります（エンコーディングに関係なく）。そのような検証者を非決定的な決定者に変換しようとすると、やや興味深いマシンになります。 TMで（TM、i）を実行すると、TMを実行することができるはずです。 そうではありません 入力の停止私はマシンを通る非ハーティングパスは存在しませんが、停止状態につながるパスには、常に別の長いパスがあります（より大きなnの推測に対応）。その実行時間。本質的に、これは、最初の非決定論的推測によって探索する必要がある無限の空間があるためです。そのようなNTMをaに変換します 決定論的 TMは、いくつかの入力をループしたり停止したりしないマシンの1つにつながります。実際、停止の問題を決定できるNTMは存在しないため、境界のあるサイズの証明書で動作する検証剤はありません。

私はディオファンティン方程式にそれほど精通していませんが、本質的に同じ問題があなたの議論に当てはまるようです。

このため、NPのNTM定義について推論する方が簡単です。有望な問題には検証剤があります（元の問題への入力のサイズに結合した多項式サイズを持つ証明書で機能するものではありません）。実際、それはどんなtmです 認識します しかし、そうではありません 決定する 一部の言語は、同じ言語の検証器に簡単に変換できます。

あなたが検証剤について考えるなら、私はあなたが彼らのサイズの点で彼らの時間の境界を与えなければならないと思います 元の問題 入力、証明書のサイズの観点からではありません。証明書のサイズで検証者が下位に縛られるように、証明書のサイズを任意に膨らませることができます。

Answer 2

私はあなたがディオファンティン方程式を解決することの意味を誤解したと思います、そして Matiyasevichのわいせつな定理.

Matiyasevichは、すべてのREセット$ s $について、整数係数$ f（n; x_1、...、x_k）$が$ n in s $が存在する場合にのみ$ n in $ x_1 $、..、 $ x_k $などの$ f（n; x_1、...、x_k）= 0 $。特に、停止の問題は典型的な再セットであるため、上記の問題を解決することは困難です。

$ x_1、... x_k $のサイズは境界があり、一般に任意に大きくなる可能性があるため、この問題で明らかな「多項式サイズの証明書」はありません。

拡張するには、整数$ x_1、...、x_k $を証明書にするにはバイナリで記述する必要があります。これらの整数は任意に大きくなる可能性があるため（$ n $に関係なく）、証明書は$ log n $で多項式ではないか、より重要なことには、計算可能な関数によって制限されていないことがあります。

$ mathsf {np} $のすべての問題には、多項式$ p（n）$（$ n $は入力のサイズ）に制限される証明書があります。したがって、$ mathsf {np} $の質問は、すべての可能なビット文字列を長さの$ p（n）$まで列挙できるため、些細なことに決定できます。一部の人が真実を返す場合。

Answer 3

あなたはにスクロールする必要があります 正式な定義:

言語$ l $は、多項式$ p $と$ q $が存在する場合にのみNPにあり、決定論的なチューリングマシン$ m $があります。

• すべての$ x $とyについて、マシン$ m $は入力$（x、y）$で時間$ p（| x |）$を実行します。
• すべての$ x in l $について、$ m（x、y）= 1 $の長さ$ q（| x |）$の文字列$ y $が存在します。
• すべての$ x not in l $とすべての文字列$ y $ of length $ q（| x |）$、$ m（x、y）= 0 $。

つまり、検証剤は非節約にも作業する必要があります。そこのどこかで、管理できない問題は失敗します（あなたの場合、ソリューション候補の長さの制限はおそらく満たされていません）、（計算可能性の意味で）より明確になっているように 意味:

NPは、多項式時間に実行される非決定的なチューリングマシンが決定できる一連の決定問題です。

Answer 4

上記の回答の詳細を提供しようとしています。

実際、この質問はジレンマの問題です。

一方では、マティエヴィッチの定理によると、ディオファンティン方程式の問題（DEP）は決定できません（Matiyesesevichの定理はヒルバートの10番目の問題に答え、チューリングの停止問題はヒルバートの10番目の問題の一般化に答えます。しかし、一方で、NPの定義（決定可能で検証可能）によると、NPには決定不可能な問題はありません。

つまり、DEPはNPではないか、DEPがNPに含まれていません。どちらもNPの定義に関するものです。

DEPがNPにない場合、それはNP（NDTM ＝非決定的チューリングマシン）の問題が解除可能で検証可能であることを意味します。つまり、p = np（ndtm）を受け入れます。

DEPがNPにある場合、NP（NTM ＝非チューリングマシン）には決定可能で決定不可能であるため、明らかに決定できます。したがって、問題は検証不可が検証可能かどうかです実際、それはp対npの有名な問題です。確かに、決定不可能は検証できないため、NPはNDTM（非決定的チューリングマシン）の代わりにNTM（非チューリングマシン）に対応します。

DEPの前提はNP（NTM）にあります。NP（NTM）は非決定論的問題（決定不可能）であり、NPの現在の定義（NDTM、決定可能で検証可能）がこの非皮膚症（策定可能）を失いました。質問する必要があると思います。

Answer 5

ディオファンティン方程式について提起したジレンマは非常に重要であると思います。なぜなら、それはNPの現在の定義で異常な何かを明らかにするからです。時間。

NPの定義に関しては、60年代に追跡できます。そこでは、多項式時間でこれらの問題を認識するために、多項式アルゴリズムを解決するために多項式アルゴリズムを解決することができなかった多くの適用可能かつ重大な問題が発見されました。 （p）、NPの概念が公開されました。

ただし、多項式時間で検証可能であると定義されているNPの現在の定義は、PとPの問題も多項式時間で検証可能であるため、PとNPを混同します。別の言葉で言えば、そのような定義は、npの本質、「nondeterminisme」の喪失につながります。その結果、それはNPを理解する際に深刻な曖昧さを引き起こします。たとえば、あなたのジレンマ。しかし、NPの定義によって、それは決定可能です、…

私たちの意見では、«p対np»を解決することの難しさは、最初に認知レベルにあります。したがって、«p対np»の洞察を得たい場合、最初は質問する必要があります。NPとは何ですか？