巴林頓又證明了，全部由門層次不超過5層的分支門構成的電路，可以解所謂的多數問題：在一串的0和1中，1是不是多數？綜合性理論學家普遍地（並且錯誤地）認為分支門限制于任何固定高度，不可能求解多數問題，更不用說嚴苛的五層限制了。

這個問題由多產數學家歐拉去解，歐拉是一位有13個孩子的父親，同時還著有80本書的數學研究成果。傳說，許多研究報告都是在第一次與第二次叫他去吃飯之間的30分鐘時間內寫出來的，他預見性地證明這種路程問題無解。數學的靈魂大力提倡分析最普通的例子。因此，歐拉不僅想為柯尼斯堡的居民，也想為各地喜歡橋樑散步的人們解決問題，他試圖解答一個普遍性的問題：「有若干河流及其分支穿過某一地區，並在其上架設任意數量的橋樑，已知河流與橋樑的布局，求是否有可能在每座橋樑只穿過一次的情況下，穿過所有的橋樑。」如果你把陸地區域看成城市，把橋樑看成公路，那麼你就可以認為，這個一般性問題與公路檢查員所面臨的問題相同。

當n的值小時（也就是說，對於簡單的問題），已知的多項式函數可以等於甚至超過已知的指數函數，但是當n的值大時，任何指數函數都將迅速地超過任何多項式函數。例如，當n等於2時，多項式函數n2等於4，它等於指數函數2n。但當n等於10時，n2隻等於100，而2n卻會像火箭上天那樣猛增到1，024。毫無疑問，指數函數的增加會大大超過多項式函數的增加，這曾使托馬斯·馬爾薩斯感到憂慮，因為他發現人類的人口是以指數函數增長的，而與之相比，食物的供應則只以多項式函數增長。

演算法的功能之一是其能用於一個問題的所有實例。例如加法演算法可以算出任何兩個整數的和。你雖然花費時間去詳盡寫出一種演算法的全部細節，但你卻得到了一種能夠保證工作的方法。計算機的程序或是單一的演算法或是系列的演算法。如果沒有指令告訴該演算法的每一步驟應該做些什麼，那麼計算機就同不能模擬系好鞋帶一樣，也不能進行兩數相加的計算。程序設計員的作用在於編好完整的指令，換句話說，要編好完整的演算法。當程序設計員責怪其程序中的錯誤時，他的意思是指在編寫詳盡演算法或把演算法譯成計算機語言時，他犯了一個錯誤。

在旅行推銷員問題中，對效率很低的窮舉搜索法仍無簡捷的方法。比方說，你仍不能計數出連接于每條公路的城市數，並根據這些數是奇數還是偶數來做出某種結論，或者就此而言，也不能根據這些數的其他性質得出結論。而且，這還不僅是我們不知道尋求那些性質的問題。還有可能是這些性質本來就不存在。這正是綜合性理論學家都在努力證明的問題。

要把歐拉的分析應用於一般情況，需要數出每處陸地區域的橋樑數。由於每座橋樑都要連接兩處陸地區域，因此橋樑要兩倍計數。如果橋樑數為n，那麼歐拉的分析需要2n個步驟。橋樑的計數可以作為一種演算法列出公式，而且它將成為一種非常有效的演算法，因為雖然問題變得越來越複雜，演算所花費的時間卻僅多了一倍。而從另一方面看，所有可能旅程的窮舉搜索法則將成指數地迅速增長為2n。

據說，伊曼紐爾·坎特習慣於環繞城市進行長路程的保健散步運動，而且居民們也都想知道，是否可能有一條進行散步的來迴路線，可以穿過所有7座橋樑，而每座橋樑只能穿過一次。由於橋樑的數目很小，這個問題可以用列舉所有可能路線的方法（否定的方法）去求解，也就是說採用類似於旅行推銷員這個小問題的、沒有預見性的窮舉法。

當然，他會立即出錯——而且是個大錯——因為https://read.99csw.com你沒有考慮一些看來好像是理所當然不成問題的基本步驟，就像系鞋帶時理所當然要握住鞋帶的塑料包頭，而不是握住它的中部一樣。如果你詳詳細細地寫出，那麼你就會得到一個有關係鞋帶的規則系統，而這個規則系統不過是一個循序漸進的程序，在這個程序中，每一步都說得很明確，你可以按部就班地解決每個問題。每個步驟都要規定得清清楚楚，其間不允許留下任何靠可能、直覺、經驗、解釋或想象等方法來處理的細節。

然而，隨著人群問題的人數增加，用於已知解法的電路大小（也是邏輯門的數目）將按指數方式激增。如果數學家們能夠證明，對於任何可能已知或未知解法，電路必按指數方式增大，那麼他們就能證明人群問題沒有快速演算法。

旅行推銷員問題不僅僅是惟一的計算問題，許多數學家都不理解其快速演算法。還有一整套叫做NP-完全的問題，對於這類問題，人們僅知道其計算所需時間以指數方式激增。①在NP-完全的問題中，另有一個眾所周知的例子稱為人群問題：已知有一大群人，比方說，共100人，他們之間是否有許多人，比方說，有50個人，全都彼此認識嗎？

在形式邏輯中（和日常的英語中），詞「非」加在前面可把真語句變成假語句，而且反過來也一樣。把它換成布爾代數的術語，則是「非」可把1轉換為0，0轉換為1。因此，「非」邏輯門有一根輸入引線，並把輸入信號轉變為其相反信號，即如果輸入是1，則輸為0，而如果輸入為0，則輸出就為1。

必須強調的是，演算法的用戶不管是一部機器還是一個人，不需要對演算法做出判斷。例如，加法演算法的使用，不需要「什麼是數字」這一概念。要應用演算法時，你可以盲目地按照法則進行。比方說，你不必知道，5是跟在4之後，7是大於3等等，甚至你也不必知道你是在使用十進位的數制。哲學文獻中已有許多篇幅談論過，就計算機的思考能力而言，缺乏判斷會意味著什麼。但是，探討這樣一個引人興趣的說法則使我們離題太遠了。

工業上每天都出現許多計算問題，若用任何已知的方法去解，則太費時間，現在都例行地由計算機去著手解決。然而工業需要的是對這些問題的解法，而計算機常常牽扯到程序設計人員的水平，他們往往不能編出最佳程序。其中有許多是眾所周知的使旅行推銷員感到為難的問題；已知一個城市與公路網路，要找一條推銷員在往返旅程中到每個城市去一次的最短路線。僅有一種已知的演算法用來解這種旅行推銷員問題，就是可靠的逐步試探法，這種方法費力，缺乏預見性，只是對每一種可能性都進行嘗試。看來，數學並未減輕威利·洛曼的煩惱。

________

從某種基本意義上講，計算機和數學家只是不容易識別的圖靈計算機，知道這一點也許令人泄氣。但在另一方面，從表面上看過於簡單的圖靈計算機，由於證明能夠解各種各樣的計算問題，從而又可被認為是鼓舞人心的。數學家與計算機之間理論上的相似性不僅適用於他們能解出的各種問題，而且也適用於他們不能解出的各種問題。

1985年8月，美國麻省理工學院計算機學科研究生約翰·哈斯特德採用了姚的基本理論，但是簡化了他的論據。哈斯特德說道：「在工作過程中，我獲得了比較有力的結果。（在這種有限制的問題中）我們所知道如何設計的最小電路並不比我在理論上曾經證明它們應有的規模大出很多。」後來的證明都表明：數學家們實際上知道如何設計出並不比他們在理論上所推斷的最佳電路差很多的電路。對於這些有限制的問題來說，不是數學上的無read.99csw.com知，而是問題的本身排除了快速的解法。

詞「或」也是用於連接語句成為複合語句，但只要一個或幾個組元都是真的，則其複合組元也是真的。如果朱爾斯或者吉姆（或者他們兩人）在吃他們各自的食物，那麼「朱爾斯吃豆腐或吉姆吃多夫條形麵包」才是真語句。同樣地，「或」門可以接受兩個或幾個信號輸入，但只要至少輸入之一是1時，則其輸出也是1。

「你可以解這種問題，」美國麻省理工學院綜合性理論學家邁克爾·賽普澤說道，「先投出 100個點，每點表示一個人，然後在相應的彼此認識的兩人的點之間劃一直線。」於是你將希望這組的50個點全都有連線。賽普澤接著又說：「看起來它很像一個有關計算機方面的重大問題，然而它不是。我們知道，如何去解這種問題，僅有的一種方法實質上是查看50人小組的所有連線，它們的數量非常多，就像10的29次方。要解出這個問題，即使應用快速的計算機，也要好幾百年。」

你可曾記得，在你讀小學時，你的英語老師讓你制定出一整套令人厭煩的規定，去做諸如系鞋帶一類枯燥無味的瑣事，然後老師叫約翰尼·懷斯蓋嚴格按照你的規定去系他的鞋帶（與此同時，這個討厭的老師還會讓你大聲念你的那一套規定）。

NP-完全的問題還有一個醒目的特點，如果這類問題中的任何一個問題能夠用快速演算法求解，那麼其他問題也都能用此法解出。而且，對於某類NP-完全問題採用快速演算法毫不費力，而且稍加改進，就可用於解任何其他NP-完全問題。例如，如果人們發現了一種用於解旅行推銷員問題的快速演算法，那麼數學家們就會自如地運用快速方法去解人群問題和所有其他的NP-完全問題。因此，旅行推銷員問題是否有快速解法與NP-完全問題是否真的像看上去那樣難這一較大問題有關。

蘇聯莫斯科大學的兩位數學家阿·拉茲波洛夫和阿·安德烈耶夫在不限制電路深度但卻限制所進行的運算方面取得了很大的成功。拉茲波洛夫又證明了如果不允許用「非」門的話，則用於人群問題的電路規模的增長將快于任何多項式的增長。而且，數學家們還在這裏對這一結果做了改進，它表明電路必須是按指數方式增大。安德烈耶夫通過禁止用「非」門還能夠證明另一類問題也需要大規模電路。

數學的行家對於快速（與可用）的演算法和慢速（與不可用）的演算法都有嚴格的確定方法。假設數字n是某問題大小的量度（對於旅行推銷員問題，n是城市與公路數目的量度）。對於快速的演算法，隨著計算問題規模的增大，完成演算法所需的時間的增長不會大於n（表示計算規模）的某個多項式。多項式是一種數學函數，諸如2n（加倍）、3n（3倍）、n2（平方）、n3（立方）、3n10和64n100等。而對於慢速的演算法，例如用於解旅行推銷員問題的窮舉搜索法，則其執行時間將按問題規模增加的指數增加，即2n、6n或12n等。

在計算機中，任何數目的「與」門、「或」門和「非」門都可以連接在一起，形成一種電路。例如下圖示出4個「與」門和1個「或」門組成的一種小型電路，它可以用來求解人群問題的普通實例：在4個人的一組中，有3個人是朋友嗎？

為了解柯尼斯堡橋樑問題，歐拉用幾何線表示每座橋樑，用幾何點表示每塊陸地。

歐拉關於任意數橋樑與任意數陸地區域的結論要比歸納成普通的常識重要得多，認識到這一點很重要。我們的推論只是簡要地說明，如果歐拉所斷定的條件不能夠滿足，則非重複的旅行將是不可能的。歐拉的結論是很強有力的，直觀上卻不是很明九九藏書顯的：他證明了，如果這一簡單條件得到滿足，也就是說，當陸地區域數為0或2，而且連接它們的橋樑數為奇數時，非重複的行程總是可能的。

數學家們還不知道如何開始這樣的證明，已經轉而考慮另一特殊的問題，這就是通常都有快速演算法的奇偶函數，而且他們還試圖以某些基本方式來限制電路，使得快速演算法不再產生作用。（奇偶函數可在一串的0與1中確定是否產生偶數或奇數。）這種方法看來也許有些怪，其實它並不怪。數學家們對於如何證明電路必須是大型的了解甚少，因此為此目的而做的任何證明，甚至是某種人為的情況，也都將會有所進展，而且可以提供證明真正論點所需的數學工具。賽普澤說道：「這是數學中的普通方法。如果問題很大，可試圖把它限制到某些範圍，並求解其中一部分，希望這種分部解法使人們對原來的問題會有更深的了解。」

每一個邏輯門都能完成3種基本運算中的1種：「非」、「與」或「或」。這3種運算的名稱都是根據布爾代數中已經使用的詞「非」、「與」和「或」而得來的。布爾代數是19世紀40年代由喬治·布爾研究出來的一種開拓性的形式邏輯體系。布爾是一個貧窮補鞋匠的兒子，他自學數學，研究出符號邏輯體系，其中1表示真的，0表示假的。儘管布爾的研究工作使他獲得了愛爾蘭科克大學的數學教授職位，但直到100多年後第一部電子計算機問世之後，他的邏輯體系才得到數學界的完全賞識。

當數學家們談到保證解題方法時，他們的意思就是指演算法。不要由於「演算法」（algorithm）這個英語單詞的發音令人生畏而擯棄它，它是9世紀波斯數學家阿布·賈法爾·穆罕默德·伊本穆薩·阿爾霍瓦里米的姓氏音譯轉訛而來的，他的語義遺產還包含有單詞代數（algebra）在內。演算法的音難讀但不難懂。你早已了解什麼是演算法的直觀概念。

當然，詞「與」用於連接單個語句成為複合語句，即如果每個組元都是真的，那麼複合組元也是真的。現舉一簡單例子，「朱爾斯吃豆腐與吉姆吃多夫條形麵包」，只有當朱爾斯和吉姆兩個人都在吃上述的食物時，它才是一個真實語句。由於同樣的理由，「與」門可接受兩個或多個信號輸入，如果所有的輸入都是1時，那麼輸出也是1，否則，則輸出為0。

這種論點動搖了一些數學家的想法，他們認為他們也許能夠證明旅行推銷員問題及同類的其他問題都不會有快速解法——從來就沒有過——即使未來讓愛因斯坦一類大師來絞腦汁也不會有。他們怎麼會提出要證明這樣的問題？

布爾代數的絕妙之處在於，1和0不僅表示真的和假的，而且還可以表示任何兩種不同的狀態。例如在旅行推銷員問題中，0和1可以表示城市之間的相應關係：如果兩個城市由一條公路連接，則以1表示，如果它們沒有公路連接，則以0表示。在人群的問題中，1可以表示兩個人成為朋友的狀態（或者在該問題的圖解表示法中，表示由一條線連接的兩點），0表示他們不是朋友的狀態（表示沒有線連接的兩點）。

過去15年內，數學家們都感到迷惘，他們尋求巧妙的、較快的演算法都告失敗，這是由於他們無知呢，還是這種問題本身存在內在的困難？按照當前的知識水平，暫時還沒有較快的演算法，甚至在理論上也沒有。目前還沒有人能夠證明這一點。對證明的研究已是理論計算機科學中最為熱門的課題，而且在這個領域中工作的數學家已被公認為是複合型理論學家。

歐拉已能證明，只有當點（陸地區域）為0或2，形成的線（橋樑）為奇數時，才可以進行穿過所有橋樑的非重複散步。你只要稍加思考就可支持九*九*藏*書這一結論。如果你穿過一座橋樑到另一處陸地去，必須還有一座橋樑讓你離去，否則你將被困在那裡。大片陸地需帶有偶數橋樑才能確保那裡有一條進去的路，另有一條離去的路。要是大片陸地只帶有奇數的橋樑，那只有在旅程的終點（在那裡你不需要一座橋樑離去）和旅程的起點（在那裡你不需要一座橋樑進去）才有可能進行非重複的旅行。由於只有一個起點和一個終點，因此只有兩處陸地才能有奇數的橋樑。在柯尼斯堡，4處陸地區域的每一處都連接了奇數的橋樑，即使沒有比較嚴格的來回旅程條件，那麼完全的非重複散步顯然是不可能的。

這些成就使這一領域樂觀起來，雖然還沒有人知道怎樣才能減少對電路的限制並證明在無限制的情況下，旅行推銷員的問題的確很難。「還有很長的路程要走，」賽普澤這樣說道，「6年以前，我曾與人打過賭，我希望他還記住，將在2000年得出證明。我仍然信心十足，還有12年多的時間。」格雷厄姆還抱有更大的希望：「在以後3年內得到證明也不會讓我吃驚。」

在這幅圖中，歐拉已把問題簡化成基本線條，去掉了所有無關緊要的內容。比方說，線與點的表示無法區別橋樑是寬還是窄，是特定的橋樑還是連接同一陸地區域的其他橋樑，是大塊陸地還是小塊陸地，乃至是島嶼還是河岸等。這些區別也許在其他方面非常重要，但與窮舉的非重複性散步方法無關。這是一種漂亮的數學表示法：它僅需要在手邊保留那些有關的情況，從而使數學家免受枝節問題的干擾，更能集中注意力于問題本身。

數學家們都不大關心旅行推銷員這一專題。對於一系列較小的城市與公路網路，由於沒有多少可能的路線需要審查，因而找到解法是很容易的。甚至對於大的城市與公路網路，那也可能幸運地或者偶然地找到最佳的路程。當數學家們宣稱某問題實際上是不可解時，他們的意思是，僅僅知道保證解法的許多方法，就像窮舉搜索所有可能性的方法一樣低效，即使對於最高級的超級計算機來說，這種窮舉搜索法也是太慢的。

在這一領域內，早期的工作限制了電路的研究工作的深度，這裏的深度是指邏輯門的層次數目。1981年取得了第一批成果，當時美國卡內基-梅隆大學的賽普澤及其兩位同事證明了，如果他們限制用於奇偶函數的電路深度，那麼電路寬度的擴展快于任何多項式。1985年，美國斯坦福大學的安德魯·姚在這方面取得了更驚人的研究成果，他證明了電路的寬度不僅以超多項式的方式擴展，而且還以指數的方式擴展，這表明這種問題雖然受到人為的限制，但也有內在的困難。

目前的工作都集中在邏輯門上，它已被認為是計算機硬體中最基本的單元。在電子計算機內，邏輯門是一種組件，由任意數目的輸入引線與一根輸出引線組成。邏輯門也是一種二進位器件：每根引線中的信號都被認為或是1、或是0。（在電子學術語中，高電平對應於1，低電平對應於0。）

儘管人們普遍樂觀，但在綜合性理論方面（數學的一個分支學科，它表述了問題的難度）的研究人員，以他們的直覺已經知道他們會失敗的。1985年冬天，美國麻省理工學院的數學研究生戴維·巴林頓曾證明，計算機能夠運算的某些原始表示法會比該領域中任何人所能設想的更有功效。這種原始表示法不包含「與」門、「或」門和「非」門，但卻包含一個分支門，它也有兩根輸出引線。當分支門受到觸發時，如果輸入信號具有一定的指定值，則分支門就會沿兩根引線之一送出一個信號；對於所有其他輸入信號，分支門沿另一根引線送出一個信號。換句話說，分支門能夠處理計算機程序中的語句，諸如「如果x=5，htｔpｓ://ｒeａd.99ｃｓw.ｃｏm轉向步驟4；對於所有其他x，轉向步驟7」。

巴林頓說道：「我的證明很簡單，但它令人驚奇，因為他們總是認為我所試圖證明的都是假的。」巴林頓的結果也許沒有多少實際用途——他又說：「除了它可以讓我在一所好大學獲得一個教師職位之外。」而且它還可以說服數學家們不要在複雜的綜合性理論領域中如此自信。

① 如果你一定要知道的話，NP表示非決定性的多項式，而complete一詞則意味著這些問題是該類問題中最難的。

姚的成果很快地傳遍了數學界。賽普澤這樣說道：「每個人都認為這個結果很滿意，但也是非常複雜的。」姚的方法為他人鋪平了道路，好幾個研究人員很快地對他的結果做了改進。美國電話電報公司貝爾實驗室數學科學部主任羅納德·格雷厄姆說：「這很像開車的頭4分鐘路程，一旦有人學會它，那麼人人都可以學會它。」

美國電話電報公司的戴維·約翰遜說道：「我認為，現在每位數學家實際上都認為NP-完全問題有內在的困難。」約翰遜是這一領域的權威人士，著有《計算機和難處理性：NP-完全理論指南》一書。他還說：「真正的問題是證明它。」

倫哈德·歐拉1736年的研究工作，輕而易舉地回答了公路檢查員的問題。歐拉是一位29歲的普魯士數學奇才。原普魯士城市柯尼斯堡（現為蘇聯城市加里寧格勒）位於普雷蓋爾河的兩岸，並且包括克尼霍夫島以及河流岔口中部的一塊狹長陸地。城市的4個區域由7座橋樑的網路連接起來。

當然，數學家們對於計算問題的演算法要比系鞋帶更感興趣。兩個整數相加的演算法，根據小學老師教給我們的方法，是用紙和鉛筆按照如下的明確步驟進行：把整數寫成一行，一個數寫在另一個數的上方，兩數右端對齊，在它們下方劃一橫線，從右到左地進行計算，有時還「進位」1，而且照此步驟計算許多其他數的相加，也是不成問題的。這種演算法應該包括如下法則，像「如果一個數2在另一個數4的上方，可在其下寫一個數6」和「如果一個數3在另一個數6的上方，可在其下寫一個數9」等法則。

看來與旅行推銷員問題似乎有點相似的許多問題，數學家們對它們已經有所了解。例如，請考慮，一位公路檢查員，他負責檢查某段公路網，旅行推銷員可能就在這段公路網上驅車。這位檢查員渴望回家去看妻子和孩子，他想知道，是否有一條來回的路程，只須經過每條馬路一次，只經過一次。但他並不關心城市，他只是想自己能走過公路的每個路段，而且還不重複。而從另一方面來說，旅行推銷員卻不關心公路，他只想去每個城市，每個城市只去一次，這樣可把其汽車裡程減到最短。

旅行推銷員的問題、人群問題、以及所有其他NP-完全的問題，都有難以理解的共同特點：如果有人聲稱，他對於這類問題中的任何一個特殊事例已經有了解法，那麼要檢驗這個解法則是很容易的事。對於旅行推銷員問題，只要檢查所提出的旅程，並查明是否包括了每個城市一次。對於人群的問題，則要雙向檢查已被辨認全都互相認識而成群體的50個人。美國伯克利市加利福尼亞大學計算機科學教授理查德·卡普把 NP-完全的問題比作拼圖玩具：「它們可能難於組合，但是當有人向你展示一幅完全的拼圖時，你就能一下子知道問題已有正確解。」

解旅行推銷員問題，僅有已知的一種方法是按指數減慢的方法，即審查所有可能旅程的方法，這一事實意味著，在當今這個年代里，我們已不能對看來如此簡單的問題有真正的了解。綜合性理論學家總想試圖證明這個迷惑人的猜想：不管我們如何努力嘗試，我們對它都不會有任何了解，因為它就是不能理解的。