ナッシュの手紙（1955年）
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/06/16 08:14 UTC 版)
「P≠NP予想」の記事における「ナッシュの手紙（1955年）」の解説
ジョン・ナッシュは、1955年に書いたNSA宛の手紙の中で、十分複雑な暗号を破るには鍵長の指数時間を要するだろうと述べた。もしこれを証明できれば（ナッシュは証明不能と考えていたが）、今日でいうP≠NPを意味することになる。何故なら鍵候補の検証自体は多項式時間で終わるからである。
※この「ナッシュの手紙（1955年）」の解説は、「P≠NP予想」の解説の一部です。
「ナッシュの手紙（1955年）」を含む「P≠NP予想」の記事については、「P≠NP予想」の概要を参照ください。
ウィキペディア小見出し辞書の「ナッシュの手紙」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ。
- ナッシュの手紙のページへのリンク
