P vs NP
計算機科学で最も有名な未解決問題。「答えを素早く検証できる問題（NP）は、素早く解ける問題（P）でもあるのか」を問う。多くはそうでないと考えているが、証明はない。ミレニアム懸賞問題で賞金は100万ドル。
1971年にスティーブン・クックが定式化した。もしP = NPなら、暗号の大半が崩れる（RSAやAESは計算困難性の仮定に立っている）。NP完全問題（巡回セールスマン問題、SAT、ナップサック問題）は、一つが速く解ければ全部が速く解ける関係にある。現実には「難しい問題はある」と受け入れ、焼きなまし法、遺伝的アルゴリズム、線形計画緩和といったヒューリスティクスや近似で対処する。なお量子コンピューターでもこの線は動かない。BQPは別の計算量クラスだからである。