• 問題
• ソリューション
• 概要

プログラミングコミュニティまたはその周辺で時間を過ごす場合は、おそらく”P vs NP”という用語をかなり頻繁に聞くでしょう。 残念ながら、正式なコンピュータサイエンスの訓練を持つ多くでさえ、概念の弱い理解を持っ

だから、ここでは簡単で簡潔な説明です：

問題

P対NP P対NP問題は、その解決策は、すぐにコンピュータによって検証することができ、すべての問題は、すぐにコンピュータによって解決することができるかどうかを尋ねます。, （Wikipedia）

それでは、PとNPの意味を理解しましょう。

P問題はコンピュータによって簡単に解決され、NP問題は簡単に解決できませんが、潜在的な解決策を提示すれば、それが正しいかどうか

上の図からわかるように、すべてのP問題はNP問題です。 つまり、コンピュータが解決しやすい場合、解決策を検証するのは簡単です。 したがって、P対NP問題は、これら二つの問題タイプが同じかどうか、またはそれらが異なるかどうか、つまり簡単に検証されるが簡単に解決されない,つまり、潜在的な答えをすばやく検証できる問題の例がたくさんありますが、すぐには解決できません。

現在、P≠NPと表示されています。 いくつかの例を見てみましょう：

• 旅行のセールスマンは、自宅で彼の旅行を運転開始し、終了することによって、100の異なる都市を訪問したいと考えて 彼はガソリンの供給が限られているので、彼は10,000キロの合計を運転することができます。 彼はガソリンを使い果たさずにすべての都市を訪れることができるかどうかを知りたい。, （Wikipediaから）
• 農家は、異なる大衆の100個のスイカを市場に持って行きたいと考えています。 彼女は箱にスイカをパックする必要があります。 各箱は壊れないで20キロだけ握ることができます。 農家は、10箱が市場に100個のスイカをすべて運ぶのに十分であるかどうかを知る必要があります。 （Wikipediaより）

これらの問題はすべて、P対NPの陰謀を理解するための鍵である共通の特性を共有しています。

ソリューション

これがP対への答えです, NP問題は人々にとってとても興味深いです。 誰かがPがNPに等しいことを示すことができれば、それはコンピュータにとって困難な現実世界の問題を些細にするでしょう。

Summary

1. P vs.NPは、コンピュータが問題をすばやく解決できることと、提案された解決策を正しくテストできることとの間のギャップを扱います。したがって、P対NP問題は、実際にそれぞれを試すことなく、数百万、数十億、または数兆の組み合わせを試す必要がある問題を解決する方法を探すこと,
2. この問題を解決いの影響をコンピューティングそのため当社の社会

Feb7,2017-ウィキペディアの属性を追加しました。
March2,2014-混乱を避けるためにいくつかの説明をクリーンアップしました。

ノート