« 肝臓病/臓器の毛細血管も作成。肝臓再生研究へ | トップページ | 体内時計遺伝子がもつがん増殖を抑える力 »

2010年8月14日 (土)

P!=NP 予想、証明されるか ?

P!=NP 予想、証明されるか ?
2010年08月09日 slashdot

詳細は、リンクを参照して下さい。

---------------------------------------
 本家 /. 記事によれば、HP Labs の Vinay
Deolalikar 氏が P≠NP 予想の証明に
関する 100 ページに上る論文の草稿を複数
名の様々な分野の研究者に送っており、今週
中にも最終稿が公開されるとのこと。

 Scribd で公開されている論文は本人の
あずかり知らぬところでアップロードされた
ものらしく、また、Deolalikar 氏は過去
にもこの分野の論文をいくつも執筆している
ようです。

 P≠NP 予想は 2000 年にクレイ数学研究所
のミレニアム懸賞問題の一つに挙げられて
おり、100 万ドルの懸賞金がかけられて
います。

 タレコミ人は門外漢なので重要そうとしか
知りません。
 この予想それ自体の意味とか、証明の意義
とか、コメントお願いします。
---------------------------------------

100 万ドルの懸賞金すごいですね。

WIKIの解説を見ると、
---------
P=NPであれば「一方向性関数が存在しない」
ことも証明できる。
そして「一方向性関数が存在しない」ならば、
多項式時間で破れない(暗号学的に安全な)
公開鍵暗号やハッシュ関数、擬似乱数が存在
しないことが導かれる。
逆に「一方向性関数が存在する」ならば、
少なくとも多項式時間では破れない共通鍵暗号
が構成できること、擬似乱数が存在すること
が証明されている。
---------
ということで、現在使われている暗号の
安全性に関わってくるようですね。

|

« 肝臓病/臓器の毛細血管も作成。肝臓再生研究へ | トップページ | 体内時計遺伝子がもつがん増殖を抑える力 »

科学関連ニュース」カテゴリの記事

コメント

コメントを書く



(ウェブ上には掲載しません)


コメントは記事投稿者が公開するまで表示されません。



トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/210730/49143022

この記事へのトラックバック一覧です: P!=NP 予想、証明されるか ?:

« 肝臓病/臓器の毛細血管も作成。肝臓再生研究へ | トップページ | 体内時計遺伝子がもつがん増殖を抑える力 »