未解決問題 P＝NP について

資料が英語なので、意味すら理解していません。
なぜ、P=NPが未解決問題になったのでしょうか？

P=NPが成立しないと思います。
数字を当てはめても、せいぜい　
P=-0 N=+0　しか思いつきません。

それから未解決問題達を解決したら、世の中ってどうなりますか？
何か大きなメリットはあるの？

No.1 回答者： sunasearch 回答日時： 2005/06/09 12:38

簡単に言うと、難しい問題が、

P「多項式(Polynominal)に比例した時間で解けること」
と
NP「非多項式(Non-Polynominal)に比例した時間で解けること」
が同じがどうかという問題です。

多項式とはxのn乗(xが変数でnが定数)の形、
非多項式とはたとえば指数nのx乗(xが変数でnが定数)の形です。

xが大きくなるにつれて、非多項式の方が早く値が大きくなります。


世の中的には、NP=Pということが証明されれば、今まで指数時間かけないと解けなかった問題が、多項式時間で＜画期的に早く＞解けることが証明されるわけですから、世の中は一変し、ノーベル賞？間違いなしです。

No.2 回答者： Tacosan 回答日時： 2005/06/09 12:58

P とか NP というのは, それ自身で集合を表す記号です.

P というのは「多項式 (polynomial)」で, 「決定性多項式時間アルゴリズムが存在する (簡単にいうと, 与えられた問題例が特定の条件を満たしているかどうかが, 問題例の大きさの多項式で表現できる時間で判定できる)」問題の集合です.
一方, NP は「非多項式 (non-polynomial)」ではなく「非決定性多項式 (nondeterministic polynomial)」で, 「非決定性多項式時間アルゴリズムが存在する」, 言い換えると「問題例と『適切なヒント』が与えられたときに, 問題例が特定の条件を満たしているかどうかが問題例の大きさの多項式で表される時間で判定できる」問題の集合.

ちなみにこの P = NP 問題を解決したとしてもノーベル賞はもらえない (というかノーベル賞にそんなカテゴリーがない) のであしからず. Cray Research からの賞金と京都賞は間違いないでしょうが.

No.3 回答者： revolution_2005 回答日時： 2005/06/09 13:05

専門的なことなので、凄く簡単に説明すると、Pは現実的な時間で解ける問題、NPは現実的な時間で解けないと言われている問題のことです。

例えば、巡回セールスマン問題というものがあります。この問題は、N都市あって、ある都市から出発して、すべての都市を一度も重複せずに回って最初の都市に戻る最短の距離はどれかという問題です。

例をあげると、東京、大阪、北海道、沖縄の４都道府県をどう回れば最短距離になるかということです。

これは、全部の通り方を調べれば必ず答えを見つけることが出来ます。ですが、たった30都市になるだけで、現在ある最高のスーパーコンピュータでも、全通りを計算するのに何百兆年とかかってしまいます。

とても現実的な時間では解けないので、NP問題と言われています。

逆に、解の公式など、公式によって現実的な時間で解ける問題がP問題なのです。

それで、仮定されていることが、NP問題は実はP問題であるということです。つまり、現在NP問題と言われているものには、現実的な時間で解くための公式が存在し、P＝NPになるという仮定です。

このようなNP問題は現在巡回セールスマン問題以外にも、100近く存在し、もし一つでも解けたらノーベル賞ものです。世の中も、例えばこの巡回セールスマン問題がP問題と分かったら、最短経路が関係するあらゆるものが画期的になるでしょう。

この回答への補足

なるほど。
P=NP問題が解決したら、素晴らしい未来が見えそうですね。

難しそうですが、解決される可能性はあるのでしょうか？

補足日時：2005/06/09 14:36

No.4 ベストアンサー 回答者： revolution_2005 回答日時： 2005/06/09 21:50

＞難しそうですが、解決される可能性はあるのでしょうか？

難しいですね。1971年から約35年、世界中の研究者たちがトライしていますが、未だ解決していなく、懸賞金もかかっていますね。

そのため、P≠NPであると、現在では言われています。ですが、これもP＝NPであるということを証明するのと同様に、証明されていません。

難しいですが、フェルマーの最終定理のように、そのうち誰かがパッと解いちゃう可能性もあります。

＊フェルマーの最終定理とは、17世紀の天才数学者がフェルマーが世に投げかけた問題で、x^n+y^n=z^n（n≧3)以上となるようなものは存在しないというものを証明する問題です。
彼は、問題を解くと本の片隅に書く癖があって、この問題も同様に片隅に書こうとしましたが、分量が多すぎて、とても片隅には書けないと残したまま亡くなってしまい（現在では、彼には解けていなかったという意見が大多数を占めています）、それから300年以上もの間世界中の天才数学者たちを悩ませました。
1987年から8年かかって研究し続けた天才数学者ワイルズによって、200ページに渡る証明式で、ようやく証明された問題です。

これを機会に、興味を持たれたのなら、色々検索してみてください。そして、是非チャレンジしてみてください。ひょっとすると、貴方がP＝NPであることを証明するかもしれませんよ。

No.5 回答者： wps_2005 回答日時： 2005/06/12 14:55

#3の

> このようなNP問題は現在巡回セールスマン問題以外にも、100近く存在し、
> もし一つでも解けたらノーベル賞ものです。
という見解にコメントします。

「一つでも解けたら」というより「一つ解けたら全て解けたも同然」なのですね。
巡回セールスマン問題をはじめとするNP-hardに属する問題は、
お互いに多項式時間で帰着可能という性質を持っていますから、
一つが解ければ、さらに多項式時間をかけることで、
NP-hardに属するすべての問題が解けるということです。

100近く(100以上?)もあるといわれているNP-hardに属する問題に
世界中の学者が挑みながら、どれ一つとして多項式時間の解法が
完成されないという事実が、P≠NPではないかという予想の
信憑性を高めているわけです。(しかし証明はされていません)

ちなみに、NP-hardに属する問題といっても、全組み合わせを列挙するしか
方法がないわけではありません。全列挙では30都市も無理というのは
#3でかかれている通り事実ですが、現在では、効率的な解法の研究により
１万数千都市問題を厳密に解いたという例があります。