ウィキペディアの記事を読みましたが、正確に NP 問題とは何かを理解できませんでした。誰か私にそれらについて教えてもらえますか? また、それらと P 問題との関係は何ですか?
2 に答える
8
NP 問題は、提案された解が与えられると、その解を多項式時間で検証できる問題です。たとえば、大学のコースのリストがあり、コースが競合しないようにスケジュールを作成する必要がある場合、それは非常に難しい作業です (複雑さの点で)。ただし、提案されたスケジュールがあれば、その正確性を簡単に検証できます。
暗号化の分野からのもう 1 つの重要な例: 2 つの非常に大きな素数を乗算した結果である数値が与えられた場合、その結果のみに基づいてこれらの素数を見つけることは非常に困難です。ただし、 2 つの数値が与えられた場合、解を確認する (乗算して比較する) のは非常に簡単です。
P ではなく NP にある例 (つまり、解決策を見つけるのが難しい問題) を意図的に選択したので、違いを理解できます。簡単に解決できるすべての問題は、検証も簡単です。解決して比較するだけです。つまり、P は NP の部分集合です。
于 2010-08-17T10:04:41.557 に答える
0
Piccolo のリンクの方が便利なので、本当の答えではありませんが、HP の研究者は、P != NP が証明されたと主張しています。論文は次のとおりです。
www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp12pt.pdf
まだ承認されていませんが、100 万ドルの幸運を祈っています。
于 2010-08-17T10:09:58.463 に答える