2000年初，美國克雷數學研究所標明了7個“千禧年大獎難題”：NP完全問題、霍奇猜想、龐加萊猜想、黎曼猜想、楊-米爾斯存在性和品質缺口、納衛爾-斯托克方程和BSD猜想。NP完全問題位于這個數學難題清單的第一項，是計算機科學領域最大的難題，也可能是所有數學問題中最難的一項。P完全問題即P=NP?問題由史蒂芬·庫克在1971首次提出，它是七大千禧年大獎問題中最年輕的問題，同時也是最好了解的一個。
什麼是P和NP？
在我們的生活中，有些數學問題可以很快地解決，比如買東西結賬；但是有些數學問題卻要花大量的時間去解決，比如下象棋。随着數學和計算機科學的發展，針對于部分比較難解決的數學問題，人們想出了更好的算法，是以解決它們需要的時間就變少了。将問題分為快速解決和慢速解決兩種的話，加減乘除是可以快速解決的問題，而下象棋是慢速解決的問題，當然還有許多的問題，我們不清楚應該将它們分于哪一類。于是我們就用了包含P與NP的更精準的定義去分類這些數學問題。
P問題包含所有可以被計算機程式快速解決的問題，比如加減乘除。NP問題是指如果給出一組問題的答案，你至少可以在合理的時間裡檢查這個答案是否正确。例如給定一個數41607317，如果對這個較大數做質因數分解，是有些難度的。但是如果給出一個可能的答案比如8699和4783，你可以通過将兩個數相乘對比原來的大數，很快地得出8699和4783這兩個數是正确答案。世界上有很多的問題，我們很難去找到它的答案，但是如果給出了答案，驗證這個答案是否正确卻是相對簡單的。例如，做出數獨的答案，可以很簡單的驗證結果的正誤，但是我們至今沒有找到一個可以完美解決所有數獨問題的最優途徑（想象1000×1000級的數獨，而不是9×9的），做數獨往往還是用試數的方法（即枚舉法）。
毫無疑問，NP問題包含P問題，因為對于P問題隻需按部就班地算出問題的答案進行對比就可以了。
最難的NP問題與NP的外界
所有人都認為NP所包含的問題比P所包含的問題要多，即使有些問題還沒有被發現，當然現在還沒有人能夠證明這一點。數學家發現很多NP問題其實是互通的，比如數獨問題的本質和蛋白質折疊問題是一樣的，如果你能找到解決數獨問題的最優算法，蛋白質折疊這一21世紀最重要的生物學問題也将迎刃而解。數獨和蛋白質折疊問題屬于NP中的一個下屬分類NPC（NP-Complete）問題。NPC問題是NP中最難的一部分，這些問題的複雜性（解決問題需要的時間和空間）與整個類的複雜性相關聯，如果我們能快速解決某一NPC問題，那麼所有的NP問題都能快速解開。
NP問題需要花很長的時間去求解，但是很容易驗證結果的正确性。在NP之外，還存在着一些問題，驗證這些問題的結果甚至都是不可能的，例如，我們很難判斷象棋中的某一步是不是最好的。還有Co-NP問題，與NP問題不同的是，Co-NP問題可以在合理的時間内很容易地排出錯誤解，而不是驗證正确解。Co-NP問題與NP問題是否是互通的，我們也不得而知。除此之外，還有非常多的問題分類，每一個分類都需要花費大量的時間去解釋。
P=NP？
NP是舉足輕重的，因為它包含了一些非常重要的問題，比如：旅行商問題（給定一系列城市和每對城市之間的距離，求解通路每一座城市一次并回到起始城市的最短回路），電路設計問題和資料庫問題等，如果這些問題得到解決，我們的生活将會有翻天覆地的變化。是以，數學家們一直積極地解決各種數學問題。在這個努力的過程中，我們有時會幸運地發現一些NP問題實際上是P問題，我們就找到了解決這個問題的捷徑，同時仍有很多的NP問題還不能被歸類為P。科學家開始思考：NP中的所有問題最終都會變成P問題嗎？還是有些NP問題就是比P問題難解決的多？這就是著名的P=NP？問題。
解決P=NP猜想的方法有兩種，一種是找到NP問題的解決算法，那麼所有的NP問題就都可以解決了；另一種就是從數學理論上證明這樣的算法不存在。但是現在的很多數學家在證明這一問題上存在誤區，他們往往假設一種可能的解決算法，然後設法證明這種算法的錯誤性或不存在。實際上證明P=NP問題本身就是NP問題之一，這讓我們感到更加的困惑。
如果P=NP，那麼我們就能找到簡單的解決問題的方法，換言之，就是人類在解決複雜問題的時候是有捷徑的。計算機一下子就可以變得非常的“聰明”，可以在十分混亂的局面中，快速找到一個捷徑。當獲知了所有的資訊以後，計算機可以在極短的時間裡，對證券市場、天氣、球賽結果做出非常準确的預測；計算機能夠輕松找到一個算法，來知道藝術作品是如何直擊人心的，于是計算機可以為每個人定制出他最喜愛的音樂、藝術作品。與此同時，人工智能可以快速的自我優化，意味着人類的末日可能到來了；密碼學的基礎也很容易就會被破解，我們每個人都毫無秘密可言。
P=NP嗎？數學家還沒有答案。