NPの問題は何ですか？

Question

ウィキペディアに関する記事を読みましたが、NPの問題とは何かを理解できませんでした。誰かがそれらについて私に教えてもらえますか、そしてそれらの関係とPの問題は何ですか？

Answer 1

NPの問題は、提案されたソリューションを考慮して、多項式時間内にソリューションを検証できる問題です。たとえば、大学のコースのリストがあり、コースが競合しないようにスケジュールを作成する必要がある場合、それは本当に難しいタスク（複雑さに関して）になります。でも、 与えられた 提案されたスケジュールでは、その正確性を簡単に確認できます。

暗号化の分野からのもう1つの重要な例：2つの非常に大きな素数を掛けた結果である数字を考えると、結果のみに基づいてこれらの素数を見つけることは非常に困難です。でも、 与えられた 2つの数字では、ソリューションを確認するのは非常に簡単です（それらを掛けて、比較）。

私は意図的にNPにある例を選択しましたが、P（つまり、解決策を見つけるのが難しい問題）ではなく、違いを理解できます。解決が簡単なすべての問題も検証するのが簡単です - 解決して比較するだけです。つまり、PはNPのサブセットです。

Answer 2

Piccoloのリンクがより有用であるため、実際には答えではありませんが、HPの研究者はP！= npを証明したと主張しています。ここに論文があります。

www.hpl.hp.com/personal/vinay_deolalikar/papers/pnp12pt.pdf

まだ受け入れられていませんでしたが、私は彼が1m $の幸運を祈ります。