數學與計算機
計算機產生於對"可計算性”這個數學概念的一種理論研究，而這種理論研究比計算機技術早15年以上。1931年，奧地利數學家哥德爾的一項重大發現（不完備定理），引發了數學家對“可計算性”的研究。哥德爾的發現與希爾伯特提出的一項挑戰有關（希爾伯特計劃）。
19世紀，研究數學的公理化方法獲得了成功，併成為當時的主流，這使希爾伯特大受激勵。公理化方法是說，我們可以這樣來開創一個數學分支∶先是構建一套基本假設——“公理”，然後從這套公理出發進行邏輯推導，從而產生出這個數學分支中的所有事實。這樣，"真理"就化歸為“能從公理出發而得到證明的東西”。這個數學觀點最早是由古希臘數學家泰勒斯於公元前700年前後提出的，而且它形成了古希臘數學的基礎。例如，歐幾里得在他著作《原理》中，就是首先列出5 條基本公理，然後從這些公理出發推導出所有的定理來闡述幾何學的。
公理化方法的問題在於，如何“構建”公理，這並不容易。歐幾里得的“平行”公設就引發了人們數百年的爭論，這導致了數學家研究出各種“非歐幾何”。直到19世紀後期，希爾伯特進行了一次嚴密的研究，一套完整的幾何公理才得以建立起來。
在成功地為歐幾里得幾何構建了一套合適的公理之後，希爾伯特提出，對於數學的任何其他分支都能夠“構建出”一套公理，這一想法後來被稱為希爾伯特計劃。希爾伯特希望在數學的任何領域，寫出一套基本的假設（公理），而這個數學分支中的所有事實都可以由這套公理推出，這在理論上可行的。
1931年，哥德爾的不完備定理（不完全性定理）令整個數學界為之震驚。他的發現就是這個假設並不成立。他證明在數學的任何包含初等算術的部分中，不論你寫出多少條公理，總是會存在一些正確的陳述無法從這些公理出發而得到證明。這徹底粉碎了希爾伯特計劃。數學中的情形與生活中的情形一樣，有一部分真理註定要永遠保持讓人難以捉摸的狀態。
哥德爾把可證明性的問題轉化成與之等價的關於某種從自然數到自然數的函數的可計算性的問題，從而證明了上述結果。
這就是為什麼他的定理只適用於數學中那些包含某種算術的部分。這些公理得讓人們可以做這種算術。
哥德爾證明，在任何公理化的系統中，總存在一些函數，它們在這個系統中是不可計算的。為此，他不得不建立了一種關於“可計算函數”概念的形式理論。
在哥德爾工作的基礎上，其他一些數學家開始研究可計算性的概念，試圖搞清楚到底哪些函數是可計算的，哪些不是。
注意，沒有人關注實際的計算。也沒有具體的數被涉及到。這是一項關於什麼樣的計算在原則上可以進行的純理論研究。
數學家克林、圖靈等人證明的定理，在理論上確立了製造“計算機”的可能性，這在計算機早期發展中起到了重大的作用。而那些從事這種理論研究的數學家（特別是圖靈和馮·諾伊曼）在這種新技術的發展中則起到了舉足輕重的作用。
從一開始，就有一些數學家對怎樣用計算機來幫助解數學問題十分感興趣，而且由於計算機技術而產生了許多新的數學分支——包括數值分析、逼近論、計算數論和動力系統理論。還有一些數學家，他們本著改進計算機計算方式的想法來研究計算的概念。一些這樣的早期研究導致產生了計算機科學中的新學科，如形式語言理論、算法理論、數據庫理論、人工智能和計算複雜性。正是在計算複雜性中，我們發現了一個千禧難題，其中的一位關鍵人物是庫克（Stephen Cook）。
庫克
庫克1939年出生於紐約州。1957年，庫克進入密歇根大學，學習電機工程。大學第一年，庫克選了一門計算機編程課程，並深深沉迷其中。他與一個朋友一起編寫了一個檢驗哥德巴赫猜想的程序。20 世紀50年代，計算機科學還沒有成為一門獨立的學科，但是少數數學系開設了與計算機有關的課程。庫克選修了密歇根大學開設的所有與計算機有關的課程。他對圖靈對停機問題特別感興趣。
圖靈停機問題實說，即不存在這樣一種程序，它能對任何給定的程序進行檢查以判定這個程序是不是能在有限的時間內運行結束。
1961年庫克從密歇根大學畢業後，便去哈佛大學攻讀數學博士學位。他原本計劃研讀代數學，但很快就發現自己已深受邏輯學家王浩的影響，當時王浩在哈佛大學應用科學部任教。王浩研究的是自動定理證明這個新領域，這個新學科被麥卡錫命名為人工智能。
在哈佛大學期間，庫克還看到了拉賓（Michael Rabin）在複雜性理論方面的突破性研究工作。複雜性理論的任務是分析計算過程，看看這些計算過程執行起來可以達到怎樣的有效程度。
1971年，庫克發表了題為“定理證明過程的複雜性”的論文，其中介紹了他新發現的一個理論概念，稱作NP完全性。接下來的事，都已載入史冊了。由於這個發現，庫克很快被選為加拿大皇家學會會員和美國國家科學院院士。
那麼庫克在1971年想出的這個NP完全性概念究竟是什麼呢？
一個推銷員
設想你是一位推銷員，你的大本營在A城市。你必須駕車去B、C和D這三個城市推銷商品，從A出發，最後還要回到A。為了節省汽油和時間，明智的做法是，對你的行進路線作一番規劃，使得你要走過的總路程儘可能地短。那麼你要對這三個城市進行排序，你得到的將是如下結果，
你可以很容易地挑選出一條最佳路線。
但你要去10個城市推銷呢。在這種情況下，向上面那樣羅列出所有的路線似乎不現實，你需要用計算機來幫你。很快，計算機幫你計算出，要去10個城市推銷，你一共有3628800種不同的路線可供選擇。這裡涉及階乘計算，
僅僅是10個城市，就有這麼多的路線。但由於階乘數增長得如此之快，還沒增加幾個城市，計算機也不堪重負了。例如，
數學家把以這種方式增長的數學模式稱為呈指數增長。階乘數以指數增長。
近似解
列出所有的可能性並對它們進行比較，以找出最短的路線，這是解決這個問題的一個非常天真的方法。還有一個更好的方法嗎？因為推銷員問題在工業和商業上十分重要，所以數學家使出渾身解數試圖找到其他的方法。他們的方法可歸為兩類，這兩類都涉及高深的數學。
一種方法是尋求近似解。我們不是去尋找一條總路程最小的路線，而是去尋找一條與最佳路線的長度偏差落在（比方說）5%以內的路線。
另一種方法是尋求一個準確的答案，但要全面觀察這些城市的地理情況，並設法利用這些城市的佈局特點，以減少可能路線的數目。但這種方法有個明顯的缺點，就是你得到的答案只適用於一組特定的情況。增加或減少一個城市，就得重頭再來。
1998年，一個數學家團隊找到了巡訪美國所有人口在500以上的13509個城市的最短路線。他們用由32臺奔騰PC機支持的三臺高性能多處理器科學計算機聯成一個網絡，並在這個網絡上進行了三個半月的運算。
然而，如果不考慮近似解，不考慮對一些特定的城市組合求解，那麼就沒有人知道推銷員問題的實用解答。
理論工作者登場了
推銷員問題是20世紀30年代由維也納數學家門格首次提出的。此後不久，數學家在工業和管理中發現了同樣重要的其他問題，而且同樣也不能解決。
例如，有一個過程調度問題。在這個問題中，你面對著許多工作，它們都必須完成，比方說在工廠中就會遇到這樣的情況。這些工作中有一些要在另一些工作完成之後才能做，而有一些則是能獨立完成的。你能不能把這些工作分成組，使得完成所有這些工作時間最少。每一組中的工作將被視作一個過程，即完成其中的一個工作後才能做其中的下一個工作，但各個過程可以同時進行。
現代的汽車製造就是一個很好的例子。在組裝車身的同時可以組裝發動機，但組裝發動機的各項工作必須按照一個特定的順序進行。
與推銷員問題一樣，一旦你將這些工作分了組，使得每組工作可以與所有其他組同時進行，那麼計算總時間所用的數學便是小菜一碟。你所要做的只是在每組中將完成各項工作的時間加起來，然後在這些時間中找出一個最長的。這個最長的時間就是用這種特定的分組法來完成所有工作所需的時間。問題是為了求出所需時間最少的調度安排，你必須對所有可能的分組都進行這樣的計算，而就像推銷員問題中可能路線的數目一樣，這個可能分組方式的數目隨著工序的增長而以指數增長。
當純粹數學家開始思考這個問題時，他們會問一個非常與眾不同的問題。他們說，假設推銷員問題根本不存在有效的解法（不考慮近似方法）。那麼這個問題就變成，你能證明嗎？如果能，那麼你至少知道花費大量的時間和計算資源來試圖解決它是沒有意義的。
要令人信服地證明試圖解決這個問題是浪費時間和精力，你必須給出一個紮實可靠的證明，證明不存在明顯好於蠻力法（即對所有的可能性進行試驗）的方法可以解決這個問題。
解決一個問題需要多少個步驟
理論工作者首先面對的一個問題是，找出一種方法來度量在一臺計算機上執行一項特定任務需要多長時間。以推銷員問題為例，答案（至少）依賴兩樣東西∶所使用的計算機和城市的數量。從理論上講，計算機不是一個重要的因素，關鍵在於城市的數量。
很明顯，一個問題所涉及的數據越多，花費在計算上的時間也越長。但是長出多少呢？準確地說，如果數據總量增加了一個確定的數量，計算時間會增加多少呢？例如，如果我們將數據總量翻一番，計算時間是不是也會翻一番？
既然我們關心的是計算時間的相應增長，那麼不管是兩倍、三倍還是更多，實際上的計算時間是多少是無關緊要的。在這種情況下，我們需要做的只是弄清楚這個計算所涉及的基本步驟有多少。這就把問題從度量時間轉化為對基本步驟計數了。
什麼是一個基本步驟？以算術為例，一個基本步驟就是將兩個單獨的數相加或相乘。算上進位，把兩個N位數相加至多涉及3N個基本步驟。例如，將兩個4位數相加需要3×4=12個基本步驟。
把兩個N位數相乘的標準方法涉及N^2個基本的整數對乘法，最多再加上處理進位的N個加法。一共最多有N^2＋N個基本運算。注意到表達式N^2＋N的值總是小於N^2＋N^2，即2N^2。於是，兩個N位數相乘所涉及的基本運算少於2N^2個。
加法就是所謂"線性時間過程”的一個例子。一個線性時間過程是對規模為N的數據，至多需要C×N個基本步驟來完成的過程，這裡C是某個固定的數（在心算加法的情況中，C=3）。
既然我們只是同意用基本步驟來進行分析，而不是用計算時間進行分析，我們或許應該稱之為“線性基本步驟”而不是“線性時間”。但是由於這類分析的原本目的是要了解計算機執行一個特定任務需要花多少時間，所以最初採用了“線性時間”，這就固定了下來。
我們可以假定，任何基本運算都需要相同的固定時間，那麼基本步驟的數目就直接對應於計算所花的時間。
詞組“線性時間”中的“線性”是指，如果你畫出步驟數目與數據規模之間關係的圖像，那將是一條直線。（直線的方程式將是S=CN，S是步驟數目。）
相應地，乘法是一個"平方時間"過程。一般來說，如果一個過程對規模為N的數據至多需要C×N^2個步驟來完成，其中C是某個固定的數，那麼它就被說成是以平方時間運行。
一個比線性時間過程和平方時間過程更為一般的概念是“多項式時間過程”，一個多項式時間過程是對規模為N的數據至多需要C×N^k個基本運算的過程，其中C和k是某兩個固定的數。
所有的算術四則運算（加、減、乘、除）都是多項式時間過程。
當面對一個計算過程時，理論工作者就尋找這樣一個代數表達式（例如CN、CN^2或CN^k），它能給出這一過程對於規模已知為N的數據來說，所需要的基本步驟數目的一個上界估計。他們稱這樣的表達式為這個過程的"時間複雜性函數"。多項式時間過程是以多項式表達式為時間複雜性函數的過程。
多項式時間對指數時間
大致而言，多項式時間過程是計算機能有效處理的一種過程。如果那兩個固定的數C和k都十分巨大，那麼計算時間可達數億年。不過在實際上，日常生活中往往會產生的多項式時間過程所具有的C和k的值是完全適度的，k一般是個一位數，因此它們確實能被計算機有效地處理。
還有一個類型稱為“指數時間過程”，當數據規模為N時，需要2^N個基本步驟來完成的過程（底數也可以是某個大於2的數）。
指數時間過程幾乎無法在計算機上運行，因為隨著N的增大，步驟增加速度太快。如果在一個國際象棋盤上以2^N的規律放硬幣，那麼最後一格硬幣的高度能一直伸到半人馬座的比鄰星（37萬億千米）。
對於在工業和商業中產生的幾乎所有的指數時間過程，即使要處理規模相當適度的數據，也要讓世界上最快的計算機花上比宇宙壽命還要長的時間。
顯而易見，如果對於一個特定的問題，你所知道的唯一解決方法是使用指數時間過程，那麼你將不可能解決這個問題，除非數據規模非常小。
NP問題
多項式時間過程與指數時間過程之間的鴻溝也說明了這種分類的一個明顯缺點∶它太過粗略了。數學家意識到了這一點後，便尋找中間尺度的過程複雜性。他們注意到，對於像求解推銷員問題的過程來說，困難並不是由於複雜的計算。使得問題幾乎無法解決的原因，是需要檢查的可能性的數量之多，使得完成全部過程所需要的時間長得令人絕望。
為了試圖把這種過程與一種真正複雜計算的過程區分出來，數學家提出了第三種類型∶非確定性多項式時間過程，或簡稱NP過程。由於通常的計算機都是確定性的，所以採用“非確定性”這個詞會給人們一個暗示，即這個新概念是一個理論的東西，與實際的計算基本無關。下面是它的大致思想。
設想你有一臺這樣的計算機，它能在一次計算的某些階段從許多備選的數中作出一個完全隨機的選擇。比方說，當面對推銷員問題的一個具體例子的時候，這臺計算機能從這位推銷員可以走的所有可能的路線中隨機地選出一條。為了解出這個問題，這臺計算機選出一條路線並算出相應的總距離。這條選出的路線不是最短路線的概率是極大的。但假定這臺特別的計算機具有好得不可思議的運氣，使得它總是作出最佳的選擇。於是它會在多項式時間內解決這個問題。作出一個隨機猜測並能幸運地猜中的本領，使得我們避開了可能性的數量大得令人絕望這個難題。
一般說來，如果一個問題或任務可以用一臺非確定性計算機在多項式時間內解出或完成，我們就說它是NP型的，而非確定性計算機就是能從一系列備選對象中作出一個隨機選擇而且能極其幸運地選中的計算機。
但要注意的是，這種計算機必須要檢驗它的猜測的正確性。NP類的本質在於，僅僅是可能性的巨大數量造成了困難。對於一個NP問題，檢驗一個給定的答案是否正確這件事必須是能在多項式時間內完成的。
從直覺上說，NP問題介於多項式時間問題（簡稱P問題）與指數時間問題之間。因為NP概念建立在一個完全不現實的想法上，即有一種計算機能老是作出最佳的隨機選擇，所以它是純理論的。然而它顯示出相當大的重要性。一個理由是，在工業和管理中出現的大多數指數時間問題都是NP型的。使得它們很難解決的原因並不是有關的計算很複雜，而是必須對極其大量的實質上相同的情況重複執行一種相對容易的計算。
當NP分類於20世紀60年代第一次被提出時，計算機科學家臆斷P類與NP類並不是同一個類——雖然每個P問題當然都是NP問題，但是有一些NP問題肯定不屬於P類。理由是，看來一臺運行多項式時間算法的標準計算機無論如何也不可能表現得像一臺想象的非確定性計算機作準確猜測時那樣。例如，專家們認為，如果沒有一臺假想的非確定性計算機的準確猜測能力，推銷員問題也許根本不可能在多項式時間內解決。
人人都認為這只是個時間問題∶遲早有人會給出某個可證明不屬於P類的NP問題——不是推銷員問題，就是其他什麼問題——從而證明P和NP是不同的問題類。但這件事至今沒有發生。也沒有人能證明相反的結論。於是，P對NP問題產生了。
20世紀60年代後期，這個問題已相當重要。工業與管理中的許多重要問題都被證實是NP問題。如果能證明P就是NP，那無疑將激發人們以極大的努力去找出解決這些重要問題的有效過程。
我應該指出，證明了NP與P相同，這本身並不能導致人們得出解決具體的NP問題的有效過程。它表明的只是任何NP問題在原則上可用一個多項式時間過程解決。關於這樣的一個過程可能是什麼樣的，它不一定會提供什麼線索。
這時，庫克登場了。庫克證明存在一個特殊的NP問題，它具有一種奇特的性質∶如果這個特殊的問題能用多項式時間過程解決，那麼其他任何的NP問題也能。這是一個關於什麼類型的任務可以在一臺非確定性計算機上執行的問題。
庫克證明其結論的方法是∶他顯示了怎樣可以將任意給出的NP問題轉化成他這個特殊的問題，這樣，如果他這個問題能在多項式時間內解決，那麼通過轉換，那個給出的NP問題也能。庫克將這個性質命名為NP完全性。根據庫克的定義，對於一個NP問題，如果發現了一個可以解決它的多項式時間過程將意味著，NP類中的每一個問題都可以用一個多項式時間過程解決，則這個NP問題被稱為NP完全的。
雖然庫克的問題是一個來自形式邏輯的高度理論性的問題，但沒過多久，卡普等人就證明了其他許多更為令人熟悉的NP問題也具有這個NP完全性，其中包括推銷員問題。
對工業界人士而言，發現能解決諸如推銷員問題的有效過程就意味著利潤大幅增長。這並不是說NP完全性就意味著一個問題肯定不能有效地解決。準確點說，證明一個特定的問題是NP 完全的，就對它的難度，以及你將找到一個多項式時間過程來解決它的不可能程度給出了一個尺度。下面解釋一下。
現在假設你發現你的NP問題事實上是NP完全的。那麼大多數專家就把此作為一個不值得花費時間和精力來為它尋找一個完整解的充足理由。他們轉而把自己的精力用在尋找一個好的近似通解上。因此，儘管NP分類具有高度的人為性質，但它的確有助於管理者決定把他們的研究精力投在什麼地方。
但是未被解決的P對NP問題依然潛伏在每一件事情後面。一個關於P與NP相同的證明將在原則上使得關於NP 完全性的所有研究都變得徒勞。這樣的證明還會對互聯網的安全產生嚴重的後果。因為破譯RSA密碼是一個NP問題。人們還不知道RSA加密系統的破譯問題是不是NP完全的（很可能不是），因此，用不著證明P與NP相同，也許就會研究出這個問題的一個多項式時間解法。而另一方面，如果證明了P與NP相同，那麼立即就說明RSA系統的破譯問題可以在多項式時間內解決。那樣的話，整個互聯網的安全系統將處於極不可靠的狀態。
P vs NP
P與NP是相同還是不同？發現有許多問題是NP完全的，就意味著數學家有許多種方法來試圖證明P=NP。無論哪一個NP完全問題，只要找到一個能解決它的多項式時間過程，那麼就立即得到P=NP。例如，一個解決推銷員問題的多項式時間過程，就是關於P=NP的一個證明。
不過，要證明P與NP不同，你必須去找一個你能證明不存在多項式時間過程解法的NP問題。這個問題可以是一個已知的問題。例如，如果你能證明推銷員問題肯定無法用多項式時間過程解決，那麼你就證明了P與NP並不相同。
這並不像你想的那樣簡單。取某個能解決推銷員問題的特殊過程並且證明它不是多項式時間過程，這是不夠的。證明迄今研究出的所有過程沒有一個是以多項式時間運行，也是不夠的。確切地說，你必須證明不可能存在以多項式時間解決這個問題的過程。這意味著你的證明必須考慮可以解決這個問題的任何過程，不僅僅是那些已知的，還要包括將來可能發現的任何過程。
在圈外人看來這也許有些奇怪，但是數學家已在某些情況下能證明關於這種未知的對象集合的結果。庫克對NP完全性的證明就是這樣一種結果。他證明了如果他那個特殊的NP問題可以在多項式時間內解決，那麼包括所有尚未發現的NP問題在內的任何其他NP問題都同樣可以在多項式時間內解決。然而，在證明P≠NP的情況中，沒人能證明存在某個NP問題，它無法用多項式時間過程求解。這就是P對NP問題為什麼會成為一個千禧難題。