從某種基本意義上講，計算機和數學家只是不容易識別的圖靈計算機，知道這一點也許令人泄氣。但在另一方面，從表面上看過於簡單的圖靈計算機，由於證明能夠解各種各樣的計算問題，從而又可被認為是鼓舞人心的。數學家與計算機之間理論上的相似性不僅適用於他們能解出的各種問題，而且也適用於他們不能解出的各種問題。
工業上每天都出現許多計算問題，若用任何已知的方法去解，則太費時間，現在都例行地由計算機去著手解決。然而工業需要的是對這些問題的解法，而計算機常常牽扯到程序設計人員的水平，他們往往不能編出最佳程序。其中有許多是眾所周知的使旅行推銷員感到為難的問題；已知一個城市與公路網路，要找一條推銷員在往返旅程中到每個城市去一次的最短路線。僅有一種已知的演算法用來解這種旅行推銷員問題，就是可靠的逐步試探法，這種方法費力，缺乏預見性，只是對每一種可能性都進行嘗試。看來，數學並未減輕威利·洛曼的煩惱。
過去15年內，數學家們都感到迷惘，他們尋求巧妙的、較快的演算法都告失敗，這是由於他們無知呢，還是這種問題本身存在內在的困難？按照當前的知識水平，暫時還沒有較快的演算法，甚至在理論上也沒有。目前還沒有人能夠證明這一點。對證明的研究已是理論計算機科學中最為熱門的課題，而且在這個領域中工作的數學家已被公認為是複合型理論學家。
當數學家們談到保證解題方法時，他們的意思就是指演算法。不要由於「演算法」（algorithm）這個英語單詞的發音令人生畏而擯棄它，它是9世紀波斯數學家阿布·賈法爾·穆罕默德·伊本穆薩·阿爾霍瓦里米的姓氏音譯轉訛而來的，他的語義遺產還包含有單詞代數（algebra）在內。演算法的音難讀但不難懂。你早已了解什麼是演算法的直觀概念。
你可曾記得，在你讀小學時，你的英語老師讓你制定出一整套令人厭煩的規定，去做諸如系鞋帶一類枯燥無味的瑣事，然後老師叫約翰尼·懷斯蓋嚴格按照你的規定去系他的鞋帶（與此同時，這個討厭的老師還會讓你大聲念你的那一套規定）。
當然，他會立即出錯——而且是個大錯——因為你沒有考慮一些看來好像是理所當然不成問題的基本步驟，就像系鞋帶時理所當然要握住鞋帶的塑料包頭，而不是握住它的中部一樣。如果你詳詳細細地寫出，那麼你就會得到一個有關係鞋帶的規則系統，而這個規則系統不過是一個循序漸進的程序，在這個程序中，每一步都說得很明確，你可以按部就班地解決每個問題。每個步驟都要規定得清清楚楚，其間不允許留下任何靠可能、直覺、經驗、解釋或想像等方法來處理的細節。
當然，數學家們對於計算問題的演算法要比系鞋帶更感興趣。兩個整數相加的演算法，根據小學老師教給我們的方法，是用紙和鉛筆按照如下的明確步驟進行：把整數寫成一行，一個數寫在另一個數的上方，兩數右端對齊，在它們下方劃一橫線，從右到左地進行計算，有時還「進位」1，而且照此步驟計算許多其他數的相加，也是不成問題的。這種演算法應該包括如下法則，像「如果一個數2在另一個數4的上方，可在其下寫一個數6」和「如果一個數3在另一個數6的上方，可在其下寫一個數9」等法則。
演算法的功能之一是其能用於一個問題的所有實例。例如加法演算法可以算出任何兩個整數的和。你雖然花費時間去詳盡寫出一種演算法的全部細節，但你卻得到了一種能夠保證工作的方法。計算機的程序或是單一的演算法或是系列的演算法。如果沒有指令告訴該演算法的每一步驟應該做些什麼，那麼計算機就同不能模擬系好鞋帶一樣，也不能進行兩數相加的計算。程序設計員的作用在於編好完整的指令，換句話說，要編好完整的演算法。當程序設計員責怪其程序中的錯誤時，他的意思是指在編寫詳盡演算法或把演算法譯成計算機語言時，他犯了一個錯誤。
必須強調的是，演算法的用戶不管是一部機器還是一個人，不需要對演算法做出判斷。例如，加法演算法的使用，不需要「什麼是數字」這一概念。要應用演算法時，你可以盲目地按照法則進行。比方說，你不必知道，5是跟在4之後，7是大於3等等，甚至你也不必知道你是在使用十進位的數制。哲學文獻中已有許多篇幅談論過，就計算機的思考能力而言，缺乏判斷會意味著什麼。但是，探討這樣一個引人興趣的說法則使我們離題太遠了。
數學家們都不大關心旅行推銷員這一專題。對於一系列較小的城市與公路網路，由於沒有多少可能的路線需要審查，因而找到解法是很容易的。甚至對於大的城市與公路網路，那也可能幸運地或者偶然地找到最佳的路程。當數學家們宣稱某問題實際上是不可解時，他們的意思是，僅僅知道保證解法的許多方法，就像窮舉搜索所有可能性的方法一樣低效，即使對於最高級的超級計算機來說，這種窮舉搜索法也是太慢的。
數學的行家對於快速（與可用）的演算法和慢速（與不可用）的演算法都有嚴格的確定方法。假設數字n是某問題大小的量度（對於旅行推銷員問題，n是城市與公路數目的量度）。對於快速的演算法，隨著計算問題規模的增大，完成演算法所需的時間的增長不會大於n（表示計算規模）的某個多項式。多項式是一種數學函數，諸如2n（加倍）、3n（3倍）、n2（平方）、n3（立方）、3n10和64n100等。而對於慢速的演算法，例如用於解旅行推銷員問題的窮舉搜索法，則其執行時間將按問題規模增加的指數增加，即2n、6n或12n等。
當n的值小時（也就是說，對於簡單的問題），已知的多項式函數可以等於甚至超過已知的指數函數，但是當n的值大時，任何指數函數都將迅速地超過任何多項式函數。例如，當n等於2時，多項式函數n2等於4，它等於指數函數2n。但當n等於10時，n2隻等於100，而2n卻會像火箭上天那樣猛增到1，024。毫無疑問，指數函數的增加會大大超過多項式函數的增加，這曾使托馬斯·馬爾薩斯感到憂慮，因為他發現人類的人口是以指數函數增長的，而與之相比，食物的供應則只以多項式函數增長。
解旅行推銷員問題，僅有已知的一種方法是按指數減慢的方法，即審查所有可能旅程的方法，這一事實意味著，在當今這個年代裡，我們已不能對看來如此簡單的問題有真正的了解。綜合性理論學家總想試圖證明這個迷惑人的猜想：不管我們如何努力嘗試，我們對它都不會有任何了解，因為它就是不能理解的。
看來與旅行推銷員問題似乎有點相似的許多問題，數學家們對它們已經有所了解。例如，請考慮，一位公路檢查員，他負責檢查某段公路網，旅行推銷員可能就在這段公路網上驅車。這位檢查員渴望回家去看妻子和孩子，他想知道，是否有一條來回的路程，只須經過每條馬路一次，只經過一次。但他並不關心城市，他只是想自己能走過公路的每個路段，而且還不重複。而從另一方面來說，旅行推銷員卻不關心公路，他只想去每個城市，每個城市只去一次，這樣可把其汽車裡程減到最短。
倫哈德·歐拉1736年的研究工作，輕而易舉地回答了公路檢查員的問題。歐拉是一位29歲的普魯士數學奇才。原普魯士城市柯尼斯堡（現為蘇聯城市加里寧格勒）位於普雷蓋爾河的兩岸，並且包括克尼霍夫島以及河流岔口中部的一塊狹長陸地。城市的4個區域由7座橋樑的網路連接起來。
據說，伊曼紐爾·坎特習慣於環繞城市進行長路程的保健散步運動，而且居民們也都想知道，是否可能有一條進行散步的來迴路線，可以穿過所有7座橋樑，而每座橋樑只能穿過一次。由於橋樑的數目很小，這個問題可以用列舉所有可能路線的方法（否定的方法）去求解，也就是說採用類似於旅行推銷員這個小問題的、沒有預見性的窮舉法。
這個問題由多產數學家歐拉去解，歐拉是一位有13個孩子的父親，同時還著有80本書的數學研究成果。傳說，許多研究報告都是在第一次與第二次叫他去吃飯之間的30分鐘時間內寫出來的，他預見性地證明這種路程問題無解。數學的靈魂大力提倡分析最普通的例子。因此，歐拉不僅想為柯尼斯堡的居民，也想為各地喜歡橋樑散步的人們解決問題，他試圖解答一個普遍性的問題：「有若干河流及其分支穿過某一地區，並在其上架設任意數量的橋樑，已知河流與橋樑的布局，求是否有可能在每座橋樑只穿過一次的情況下，穿過所有的橋樑。」如果你把陸地區域看成城市，把橋樑看成公路，那麼你就可以認為，這個一般性問題與公路檢查員所面臨的問題相同。
為了解柯尼斯堡橋樑問題，歐拉用幾何線表示每座橋樑，用幾何點表示每塊陸地。
在這幅圖中，歐拉已把問題簡化成基本線條，去掉了所有無關緊要的內容。比方說，線與點的表示無法區別橋樑是寬還是窄，是特定的橋樑還是連接同一陸地區