P≠NP予想
1956年、クルト・ゲーデルは癌で入院していたジョン・フォン・ノイマン宛に手紙を書いた。その中で彼は定理の証明(今日ではcoNP完全であると判っている)を2次または線形時間で解けるだろうかと意見を求め、もしそれが可能なら数学の新定理の発見を自動化できるだろうと指摘した。
これに対するノイマンの返事は伝わっておらず、ノイマンは翌1957年に死去した。ハルトマニスは、この手紙がノイマンが健康だった間に出されていれば、この問題は既に解けるか研究史がもっと短縮されていたのではないかと嘆いている。
1971年にスティーブン・クックが定式化した概念で、クラスNPに属し、クラスNPに属する他の全問題が多項式時間帰着される問題をNP完全という。充足可能性問題をはじめとして、数千個以上の問題がNP完全であることが示されている。これらのNP完全問題の一つでもクラスPに属することを示せれば、P=NPとなる。