np-hard - NP や P として問題を作成する必要性は何ですか?

Question

問題をNPとPに分割する主な意図または主な用途は何ですか? これには歴史的な理由がありますか、それとも私たちを助けるためにこれらの概念を作成したのでしょうか? もしそうなら、これらはどこで私たちを助けることができますか?

Answer 1

これは複雑すぎてここで完全な答えを期待することはできませんが、簡単に言えば、実用的な観点からすると、P の問題は妥当な時間内に解決策を見つけることができる問題であり、NP の問題は次のような問題です。解の計算に時間がかかりすぎます (P != NP と仮定)。

P と NP の間の境界は、非公式に、計算を使用して効率的に解決できる問題とできない問題の間の境界と考えることができます。

これらの複雑なクラスの動機と目的について詳しく知るには、ウィキペディアhttp://en.wikipedia.org/wiki/P_versus_NP_problemを読むことから始めてください。

Answer 2

問題を P と NP に分割するという「実際的な」意図が下限だと思います。問題が NP 困難であることを証明した場合 (そして、P != NP という一般的な信念に同意した場合)、妥当な時間内に実行される問題のアルゴリズムを見つけることができないことを証明したことになります。

もっとくだけた言い方をすれば、あなたの上司があなたに 5 分で実行できるアルゴリズムを書くように頼んだとしましょう。見つからないと言うと、彼はあなたがサボっていると思うでしょう。彼が尋ねたことが NP 困難であることを彼に示せば、彼はあなたがそれを行うことができないと確信するはずです..形式主義に戻ると、近似アルゴリズムを使用して正当化できます。

これはすべて歴史的な会話です。現在、業界では、NP 完全 (SAT ソルバーなど) または PSPACE 完全 (フォーマル検証など、サイズが PSPACE 完全である) の問題を実装することがあるためです。方式）。一方、たとえばグラフィックスでは、で実行されるアルゴリズムを実装できない場合がありますn^2。nlogn時にはエッジの効いたものになることさえあります。