在17世紀，德國數學家戈特弗裡德·萊布尼茨提出了一種機器，它可以讀取任何作為輸入的數學陳述，并根據數學公理決定它是對還是錯。但是每個陳述都可以判定嗎？這個問題被稱為決策問題。

兩個世紀後，另一位德國數學家大衛·希爾伯特樂觀地宣稱，決策問題問題的答案必須是：是的，我們能夠而且将會知道任何數學問題的答案。1930年在德國哥尼斯堡的一次演講中，他說了一句名言，

Wir mussen wissen - Wir werden wissen。(我們必須知道，我們将會知道”)

但真的嗎？

數學的極限

希爾伯特的樂觀是短暫的。同年，奧地利數學家哥德爾通過證明他著名的不完全性定理，證明了我們在數學方面的知識是有限的。

下面是理解哥德爾定理的一種簡化方法：

命題S：此命題不可證。

現在，假設在數學的背景下我們可以證明S是真的。但是，這種說法本身就是錯誤的，導緻了不一緻。讓我們假設相反的情況，我們不能在數學的範圍内證明S。但這意味着S本身是正确的，數學中至少有一個命題是正确的，但不能證明它是正确的。因此，數學要麼不一緻，要麼不完整。如果我們假設它是一緻的（陳述不可能同時是真的和假的），這隻會留下數學是不完整的結論，也就是說，有真實的陳述根本不能證明是真的。

哥德爾對不完全性定理的數學證明，比我在這裡概述的要複雜得多，從根本上改變了希爾伯特宣揚的完整知識是可行的觀點(“wir werden wissen”)。換句話說，如果我們假設數學是一緻的，我們一定會發現無法證明的真實陳述。

以哥德巴赫猜想為例，根據哥德巴赫猜想，每個偶數都是兩個素數的和：

• 6 = 3 3
• 8 = 3 5
• 10 = 3 7
• 12 = 7 5，以此類推。

還沒有人找到一個反例。因為哥德爾的存在，我們知道有些真實的陳述是沒有證據的，但不幸的是，我們沒有辦法識别這些陳述。哥德巴赫猜想可能是其中之一，那麼試圖找到證據将是浪費時間。

• 哥德爾和圖靈

計算的極限

當艾倫·圖靈第一次學習哥德爾不完全性定理時，他還是劍橋大學的一名研究生。在那段時間裡，圖靈緻力于設計出能夠處理任何輸入并計算結果的機器的數學設計，就像萊布尼茨幾個世紀前設想的那樣。這些概念化的機器今天被稱為圖靈機，并被證明是現代數字計算機的藍圖。簡單地說，圖靈機可以比作一個現代計算機程序。

圖靈正在研究所謂的停機問題，可以提出如下問題：

是否有一個程序可以決定另一個程序是否會停止（完成執行）或不（永遠循環）？

圖靈證明了停機問題的答案是“不”，這樣的程序不可能存在。與哥德爾的工作相似，他的證明是一個“矛盾的證明”。假設存在一個程序halts()，它決定給定的程序是否會停止。然後我們還可以構建以下程序：

def g(): if halts(g): loop_forever() return

看這裡發生了什麼？如果g成立，g不成立，如果g不成立，g成立。不管怎樣，都有矛盾。因此，程序halts()不能存在。

哥德爾證明了數學是不完整的，圖靈證明了計算機科學在某種意義上也是“不完整的”。某些程序根本無法存在。這不僅僅是一個理論上的好奇：中止問題在今天的計算機科學中有許多實際的含義。例如，如果我們想讓編譯器為一個給定程序找到盡可能快的機器碼，我們實際上是在嘗試解決停機問題——而我們已經知道這個問題是不可解決的。

• 一個複雜的蛋白質結構-預測蛋白質如何折疊是一個NP問題。

知識的實際極限：P vs NP問題

哥德爾和圖靈通過展示一些根本無法解決的問題，證明了我們所知道的東西在理論上是有限的。但除此之外，還有一些問題我們可以在理論上解決，但不能在實踐中解決，因為計算解太耗時了。這就是我們要區分P問題和NP問題的地方。

P問題是可以在“合理時間”内解決的問題，而“合理”在這裡意味着“多項式（polynomial）”（簡化為P）。為這些問題尋找解決方案的計算複雜度随着問題輸入的大小而增加。想想乘法或排序問題。

NP問題是指不能在合理時間内解決的問題。NP是non-deterministic polynomial的縮寫，意思是一個解可以被确定，但不能被找到，計算複雜度為多項式。求解NP問題的複雜性是指數型的，而不是多項式型的，這在實際中産生了巨大的差異。NP問題的例子有最優調度、預測蛋白質如何折疊、加密消息、解決數獨難題、最優包裝（又名背包問題）。有些問題，比如尋找一個函數的離散傅裡葉變換，從NP開始，但最終以P結束，因為新的、聰明的算法的發展簡化了求解過程。

今天計算機科學中最大的未解問題之一就是P與NP的問題：P是否等于NP ？也就是說，對于我們能夠在合理的時間内确定解決方案的問題，我們是否也能夠在合理的時間内找到解決方案？

P vs NP問題如此重要，以至于它被列入了“千禧獎問題”的名單中，如果你找到了答案，你将獲得100萬美元的獎金。很難再誇大這個問題的重要性：一個P=NP的世界與一個P≠NP的世界将有根本不同。如果P=NP，那麼我們可以肯定地說，有一種更快的方法來解決數獨遊戲，或者預測蛋白質如何折疊，隻是我們還沒有找到那種方法。不用說，了解蛋白質如何折疊可能會對現實世界産生各種各樣的影響，比如了解阿爾茨海默氏症或治療癌症。

今天的大多數科學家認為P不等于NP，但我們能确定嗎？P對NP問題本身可能類似于希爾伯特的決策問題或圖靈的停止問題，這個問題可能根本沒有答案。

,