ランキング

最新記事30件


最新コメント30件

漫画


マイページ

ジャンル

RSS

検索


携帯版QRコード

※全機種に対応してるか分かりません

統計

総記事数:2497 件
総記者数:464 人
総コメント数:38,240 件

 

P≠NP問題はやっぱり解けていなかった



コンピュータ・サイエンスにおける最も重要な問題のひとつであるP≠NP問題。これが肯定的に解かれたとのニュースがネットを駆け巡ったのは8月初旬のことでした。

一億円の懸賞金がかかっており、解き方によっては世界オワタになる世紀の難問が解決されたというこの事件。
発生から一ヶ月が経とうとしているいま、この騒動がどのように収束したかをまとめました。

詳細は以下から。

ことの発端は今月6日、インド人コンピュータ科学者デオラリカーが、P≠NPであることの証明を世界中の研究者達に向けメール発信したことに始まります。

二日後の8日に、メールを送られた研究者の一人が自身のブログでそのことを明かして以降、web上では「科学界の大事件だ」「マジですごくね?」「ワケワカメ」「とりあえず暗号が安全そうで一安心」など、多種多様な反響がありました。




p_np.jpg

それ以降の騒動の詳細な内容はggrksということにして、結論から言ってしまえば、彼の証明は全く正しいものではありませんでした。

フィールズ賞受賞の大数学者テレンス・タオが、彼の証明についてコメントを出しています。
http://rjlipton.wordpress.com/2010/08/10/update-on-deolalikars-proof-that-p≠np/#comment-4885
http://rjlipton.wordpress.com/2010/08/12/fatal-flaws-in-deolalikars-proof/#comment-5223
Ttao2006.jpg

要約すると、
・彼の証明の間違いは、ちょっと修整すれば直せるというような代物でないと断言できる。
・大きな修整を加えても無理だろう。
・彼のアイディアである「各問題の性質をプロットし統計的に分析する」という方法からも、あまり希望が見出せない。
とのことです。

なんか偉い人が言ってるんだからその通りなんだろうなという感じがしますね。

まあ何にしろ「証明には重大な穴がある」というのがいま現在の大方の研究者の意見のようで、
一億円は真夏の夜の夢に終わったようです。

ソース元: http://rjlipton.wordpress.com/2010/08/10/update-on-deolalikars-proof-that-p%E2%89%A0np/#comment-4885
カテゴリ: サイエンス
2010年08月31日 04時45分39秒 Posted by Galoism ( 6,322 PV ) 勢い:2


この記事の評価
Galoism 記者の過去記事
 P≠NP問題はやっぱり解けていなかった
2010年08月31日 04時45分39秒 | PV( 6323 ) | コメント( 10 )
 海外のかわいいネコ画像16」枚
2010年09月02日 06時45分55秒 | PV( 5507 ) | コメント( 15 )
 5年ぶりにアルバムリリースのジャミロクワイ、その名曲の軌跡(※新曲動画アリ)
2010年09月03日 21時28分29秒 | PV( 5133 ) | コメント( 12 )
 ポップ・アートのススメ
2010年09月04日 12時08分04秒 | PV( 19776 ) | コメント( 13 )
 ヒトカラで人生を棒に振らないための三か条
2010年09月04日 19時18分43秒 | PV( 13055 ) | コメント( 27 )
もっと見る

コメント(リンクの記載「http://」は行えません)
1 名前:名無し@ガガリアン 2010/08/31(火)05:19:03. ID: cd1f1d76p
なんか知らんが世界が守られたならよかった
2 名前:名無し@ガガリアン 2010/08/31(火)07:06:42. ID: f3d1d97cp
つまりどうことだってばよ?
3 名前:名無し@ガガリアン 2010/08/31(火)07:37:05. ID: ce3114e2p
今の暗号はとりあえず破られない可能性が高い
4 名前:名無し@ガガリアン 2010/08/31(火)08:02:03. ID: a8ee503dp
あらゆる問題に有限回で解けるような解き方が存在するか?(大抵の問題はコンピュータである解き方を繰り返して解く)
という問題。
現在使っている暗号は因数分解を使った、有限とは程遠い問題で成り立っているわけだ。
もし存在するなら、いづれ有限回で解ける解き方が出るわけなので、暗号として使えなくなる。
暗号処理はあらゆる通信やデータ保存技術に使われているから盗み放題になり世界の終わりになるわけだ。
5 名前:名無し@ガガリアン 2010/08/31(火)09:39:33. ID: 6c1d50a2p
存在するか否かがこの証明だから、別に証明されてもすぐに世界の終わりになるわけではないけどね
6 名前:名無し@ガガリアン 2010/08/31(火)10:17:42. ID: e68690a1p
それより大数学者の容貌が俺の想像通りで安心したぜ
7 名前:名無し@ガガリアン 2010/08/31(火)11:27:30. ID: 37d327a2p
因数分解じゃなくて素因数分解じゃない?
8 名前:名無し@ガガリアン 2010/08/31(火)11:46:44. ID: 3aeaf473p
「証明には重大な穴がある」

・・・・・ゴクリ
9 名前:名無し@ガガリアン 2010/08/31(火)12:45:32. ID: d2d6b055p
P=NPならば現代の暗号はかなりやばいかもしれなくなる。ネットとかの通信にもバンバン使われてるから、まさに世界オワタになる可能性が。
10 名前:名無し@ガガリアン 2010/08/31(火)17:28:20. ID: 040836d9p
画像の墨は自分で彫ったのかな
だとしたら結構うまい