Icerain-冰雨2020-06-24 10:29:26這個看似簡單的一個問題，實際上是理論計算機領域最大的未解難題。
2000年，在參考了一個世紀前希爾伯特提出的23個問題的做法之後，克雷數學研究所釋出了七道千禧年大獎難題，總價值七百萬美金。解答出任何一道問題的第一個人將被授予一百萬美金的獎勵。其中一道難題正是關於解決P和NP的複雜度問題。這個問題成為了整個計算機領域的焦點，因為這個問題的結論會直接給計算機領域帶來截然不同的理論極限和發展前景。
P的定義：所有可以在多項式時間內求解的判定問題構成P類問題。而多項式的定義就是：若干個單項式相加組成的代數式。
NP的定義：問題的解可以在多項式時間內完成的問題。也就是說我們雖然不知道一個問題的解，但是如果有了解以後可以馬上證明。
目前大多數計算機科學家並不相信P=NP。根據2001年的一項調查顯示，有61%的人相信P≠NP；而2012年的調查則顯示，相信P≠NP的人達到了83%。要真的證明P ≠ NP是非常困難的，但是所有證明P = NP的嘗試都失敗了，這表明這兩類問題是互不相容的。麻省理工學院的科學家Scott Aronson寫過一篇博文，列出了P ≠ NP的10個原因，其中第9條提出了這樣一個論據，既有力地反駁了P = NP的觀點，又簡潔地描述了假如P = NP成立的結果：
如果P=NP，那麼世界將與我們通常所認為的完全不同。“創造性的飛躍”將沒有特殊價值；一旦找到問題的解，那麼在解決問題與認可解決方案之間沒有根本間隔。