P 對 NP 問題（P versus NP）

P 對 NP 是計算機科學中最著名的未解問題，也是數學的偉大未解難題之一。一句話說：如果一個問題的解容易「檢查」，那這問題是否也必定容易「求解」？P 是我們能快速求解的問題類；NP 是我們能快速檢查的問題類。這問題問：這兩類其實是否相同？幾乎所有人都相信它們不同，但沒有人證明出來。

精確地說，P 是能由確定型演算法在多項式時間內求解的判定問題集，NP 則是在給定證書時能在多項式時間內驗證的判定問題集。我們確知 P 包含於 NP。未解的問題是反向是否成立：NP 是否包含於 P，從而 P＝NP？因為 NP 完全問題是 NP 中最難的、且全都互相可歸約，這問題塌縮成單一個測試：若哪怕只有「一個」NP 完全問題（比如 SAT）有多項式時間演算法，則 P＝NP，每個 NP 問題都變得可解；若哪怕只有一個被證明需要超多項式時間，則 P 不等於 NP。這樣的演算法與這樣的下界都從未被找到。

賭注既巨大又具體。若 P＝NP，那些今天看似無望的問題——最優排程、自動定理證明、破解大量現代密碼學——全都會變得可高效求解，這正是多數研究者預期 P 不等於 NP 的一個理由，因為如此多的安全運算仰賴某些問題很難。它是克雷數學研究所七個千禧年大獎問題之一，懸賞一百萬美元。對「解決」意味著什麼要小心：證明 P 不等於 NP 會確認一道我們早已假設的屏障，而一個建構性地證明 P＝NP 可能一夜之間顛覆密碼學，不過一個非建構性的證明在實務上或許改變不大。