P≠NP予想
ジョン・ナッシュは、1955年に書いたNSA宛の手紙の中で、十分複雑な暗号を破るには鍵長の指数時間を要するだろうと述べた。もしこれを証明できれば(ナッシュは証明不能と考えていたが)、今日でいうP≠NPを意味することになる。何故なら鍵候補の検証自体は多項式時間で終わるからである。