「P!=NP 予想、証明されるか ?」記事へのコメント

どのくらいすごいかというと

[saitoh (10803)]

もし証明が正しかったら、 当然クレイ数学研究所からの賞金はもらえるとして、 チューリング賞とフィールズ賞(ぎりぎり40歳以下という制限に間に合う!)のダブル受賞じゃないでしょうか。 ゲーデル賞とかフォンノイマンメダルもいけるか。

個人的にはフェルマーの大定理よりインパクト有る

Re:どのくらいすごいかというと

[Anonymous Coward]

多分フィールズ賞ではなくて，ネヴァンリンナ賞。ICMはこの分野はこっちを出しています。あとフィールズ賞，ネヴァンリンナ賞，ガウス賞は毎年ではなく4年に1度のICM総会の時なのでタイミング的には微妙。チューリング賞は毎年だし年齢制限もないのでまあもう少ししてからでしょう。

Re:

[Anonymous Coward]

この証明とフェルマー予想のどちらが、他の法則に与える影響力が重要かまでは、
自分は不勉強にして不明だが、確かに勝るとも劣らないぐらい重要に思える。
証明されようが不完全であった事が判明しようが、続報のタレコミ熱望。

Re:どのくらいすごいかというと

[the.ACount (31144)]

フェルマー予想はもし否定されてしまったら他に与える影響が甚大だったそうだ。(自殺する数学者が出かねないと読んだことがある)
P≠NP はそこまで行ってないようだ。

--
the.ACount

Re:どのくらいすごいかというと

[Anonymous Coward]

P=NPならオンラインコマースは壊滅ですよ? (安全な一方向関数を作ることが原理的に不可能)
フェルマー予想ごとき比較にならないほど影響が大きいと思いますが。肯定的に証明されるならそれほどインパクトはないでしょうけど。

Re:どのくらいすごいかというと

[the.ACount (31144)]

今世紀中に量子計算機ができるから、それまでさ。

--
the.ACount

Re:

[Anonymous Coward]

計算量複雑性ってのは難しくて、よく知られているP, NP完全, NP困難の他にも、
多項式個数のプロセッサで構成される並列計算機が多項式時間で解決できるか(NC)とか、
量子計算機が1/3以下の間違いで多項式時間で解決できるか(BQP)とかある。

当然、暗号の研究は超並列計算機や量子計算機が登場することを見越して、NCとかBQPとか意識してやっているんだけど、ここでP!=NPが否定されたらNC!=Pなどの仮定にも影響がでてくるので量子計算機の時代になってもP!=NPかどうかの呪縛から逃げることはできない。
たぶん計算機科学をやっている人は誰も逃げられないと思う。

もし本当にP==NPが判明しても具体的なアルゴリズムが発見されない限り、すぐにSSLが崩れるとは思えないけど、P!=NPを暗黙の了解事項にしている数々の論文は全部おとされることになるでしょうね。
みんな卒業・修了・昇進できなくなる(笑)。

Re:

[Anonymous Coward]

証明されたのがP=NPだったら甚大だったろうけどP≠NPなら他への影響はそれほどないのかもね

Re:

[Anonymous Coward]

関連する研究をしていた数学者（日本人）が自殺しています。
理由は不明らしいけど。

Re:

[Anonymous Coward]

ミレニアム懸賞問題の中ではフェルマーの大定理と同じぐらい、問題の意味を説明するのは容易いと思った。

#他は高等すぎて、題意すら分からない。

Re:どのくらいすごいかというと

[kuramori (38110)]

リーマン予想は高校数学で理解できる（と、参考書に書いてあったような気がする）。
＃解けるわけじゃない。