理論與進階主題
P 與 NP 問題
P 與 NP 問題是電腦科學中最著名的開放問題：核驗一個答案，是否本質上和找到它一樣容易？P 是我們能快速求解的問題類——多項式時間，意思是執行時間像 n、n^2、n^3 這樣增長。NP 是答案可被快速驗證的問題類，哪怕找到答案本身可能很難。P 裡的每個問題也都在 NP 裡（既然能快速解出來，自然也能快速核驗）。問題在於反過來是否成立：P 是否等於 NP？
用拼圖來體會這個差別。核驗一幅拼好的圖是否正確很容易——掃一眼就行。而從一堆碎片拼起來則難得多。P = NP 就意味著：歸根結底，拼裝並不比核驗更難——凡是我們能快速辨認出好答案的問題，也存在某種巧妙而快速的辦法來構造出一個答案。多數電腦科學家強烈懷疑 P ≠ NP，即確有一些問題在「解」上就是比在「驗」上更根本地難，但懷疑不等於證明。
對現狀要誠實：這是個未解的問題。沒有人證明 P = NP，也沒有人證明 P ≠ NP；它是克雷數學研究所那七道百萬美元的千禧年大獎難題之一。其分量極其重大。倘若 P = NP，一大批當前棘手的問題——包括那些 NP 完全問題，以及守護現代通訊的大量密碼學——都將驟然變得可高效求解。倘若 P ≠ NP，我們就得到一個確鑿的證明：有些問題天生就難，從而為「退而求其次、採用近似與啟發式」這一日常做法提供了正當理由。無論哪個答案都會重塑這個領域；而此刻，誠實的表述只是：我們還不知道。
// P = problems SOLVABLE in polynomial time // NP = problems whose answer is VERIFIABLE in polynomial time // // Known: P is a subset of NP // Unknown: is NP a subset of P ? (i.e. does P = NP ?) // // Status: OPEN. No proof either way exists.
P ⊆ NP 已知；NP 是否 ⊆ P（即 P 是否 = NP）才是懸而未決的問題。
確實未解——千禧年大獎難題之一。多數專家相信 P ≠ NP，但相信不是證明，無論哪個方向的證明都將是里程碑。
又稱
另見