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

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

[saitoh (10803)]

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

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

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を暗黙の了解事項にしている数々の論文は全部おとされることになるでしょうね。
みんな卒業・修了・昇進できなくなる(笑)。