3

私は何かがNPであることを証明する方法を学んでいます。Thomas Cormenのアルゴリズムの本の紹介で、彼は、ある問題の解決策が与えられれば、何かがNPであると述べています。これは、多項式時間で正しいことを確認できます。

問題が2x+9 = 55であり、正しいx値を見つけるのにどれくらいの時間がかかるかわからないふりをしましょう。しかし、問題を解くアルゴリズムが解23を返しました。それからそれがNPであることを示すために、 23を方程式に戻すだけで、それが多項式の時間を要して55を与えたかどうかを確認できますか？ありがとう。

4

3 に答える 3

4

はい; 多項式時間でこの問題のすべてのインスタンスのすべての正解とすべての不正解の正しさを確認できる場合、問題はNPにあります。

于 2012-12-01T04:56:56.810 に答える
2

@Mehrdadの回答に情報を追加する：

NPは非決定性多項式時間を表すことに注意してください。これは、定義上、問題がNPにあるのは、非決定性チューリングマシンによって多項式的に解決できる場合に限られます。

これは、標準の計算モデル（RAMマシン/決定論的チューリングマシン）で、（@ Mehrdadが回答したように）多項式時間で回答を検証できると言うのと同じです。同等性の証明は、定義の同等性に関するウィキペディアのページで説明されています

ボーナス：
「チューリングマシンで（ポリノミリーに）検証できるものはすべてポリノミアルに解決できる」という質問と、「非決定性チューリングマシンでポリノミアルに解決できるものはすべてポリノミに解決できる」という質問も同等です。
答えはまだ不明であり、この問題はP vs NP問題として知られています。これは、コンピュータサイエンスで最も重要な未解決の質問です。

于 2012-12-01T08:10:26.567 に答える
1

上記の問題は、NPネスの最後の、そしておそらく最も識別可能なステップをカバーしていますが、問題がNPにあることを示すための3つの基本的なステップがあります。

  1. 決定問題：あなたの問題を決定問題に変えることができますか？方程式の問題の場合、決定問題は「2x + 9 = 55のようなxはありますか？」です。？

  2. 証明書：決定の質問に対する答えを特定できますか？繰り返しますが、方程式の問題の場合、答えはx=23になる可能性があります

  3. 検証：多項式時間で証明書を検証できますか。多項式時間で検証することにより、問題がNP困難ではないことがわかります。いくつかの検証手順は次のようになります：xa番号ですか？Xは55-9の半分に等しいですか？

それはあなたがあなたの問題が完全にNPにあることをあなたが知る方法です。

于 2019-04-23T04:21:27.103 に答える