P 對 NP 問題

P 對 NP 問題是確定所有 NP 問題 是否實際上是 P 問題。如果 P 和 NP 不等價，那麼 NP 問題的解決（在最壞的情況下）需要 窮舉搜尋，而如果它們等價，那麼可能存在漸近更快的演算法。

答案目前尚不清楚，但確定這個問題的狀態將對許多困難且重要的問題可能被解決的潛在速度產生巨大影響。

在電視劇NUMB3RS第一季的劇集“Uncertainty Principle”（2005 年）中，數學天才 Charlie Eppes 使用掃雷遊戲作為 P 對 NP 問題的類比。