可計算性理論和復雜性簡介
已發表: 2022-03-11你有沒有想過：你正在閱讀這篇文章的設備到底是什麼？ 電腦是什麼？
計算科學可以追溯到遠在這些現代計算設備被想像出來之前的一段時間。 在一個更常見的問題圍繞編程語言、框架和庫的行業中，我們經常認為使計算機運行的基本概念是理所當然的。
但是這些似乎擁有無窮潛力的計算機——它們有什麼限制嗎？ 有沒有電腦不能解決的問題？
在本文中，我們將通過遠離編程語言和計算機體系結構的細節來解決這些問題。 通過了解計算機和算法的力量和局限性，我們可以改進我們的思維方式，更好地推理不同的策略。
計算的抽象視圖產生的結果經受住了時間的考驗，對今天的我們來說就像它們在 1970 年代最初開發時一樣有價值。
可計算性
電腦是什麼？ 什麼是問題？
在學校裡，我們經常被教導一個問題和功能的心理模型，如下所示：
函數是您應用到輸入 x 以找到輸出 f(x) 的過程。
原來數學定義是不同的：
函數是一組有序對，其中每對的第一個元素來自集合 X（稱為域），每對的第二個元素來自集合 Y（稱為共域或範圍），並且域與範圍中的一個元素配對。
那真是滿口。 但是，這究竟是什麼意思？
這個定義告訴我們，計算機是計算功能的機器。
為什麼？
因為計算機將任意輸入轉換為某些輸出。 換句話說，他們解決問題。 函數的兩種定義，一種是我們非常熟悉的，一種是正式的，在許多實際目的上是一致的。
然而，數學定義允許我們得出有趣的結論，例如存在不可計算的函數（即不可解決的問題）：
因為，並不是每個函數都可以描述為一種算法。
遊戲規則
為了幫助我們論證，讓我們將計算機想像成機器，接受一些輸入，執行一系列操作，並在一段時間後給出一些輸出。
我們將輸入機器的字母表； 也就是說，來自某個有限集合的一組字符串。 例如，機器的字母可能是二進制（0 和 1），也可能是 ASCII 字符集。 任何有限的字符序列都是字符串，例如“0110”。
此外，我們將機器的輸出表示為二進制接受-拒絕決策，一旦機器（希望）完成其計算就交付。 這種抽像很適合早先對函數的數學定義。
給定這些參數，重要的是要表徵另一種類型：字符串集合。 也許我們關心某些機器接受的字符串集合，或者我們正在構建一台機器，它只接受特定集合中的字符串而不接受其他字符串，或者我們可能在問是否有可能設計一台機器接受某些字符串中的所有內容特定的集合，沒有其他的。
在所有這些情況下，一組字符串稱為一種語言——例如，表示偶數的所有二進製字符串的集合或具有偶數個字符的字符串的集合。 事實證明，語言，如數字，可以使用連接、聯合、交集等運算符進行操作。
一個重要的運算符是也與正則表達式一起使用的 Kleene 星號運算符。 這可以被認為是語言所有可能的力量的結合。 例如，如果我們的語言A是字符串集合 { '01', '1' }，那麼A*的一個成員就是字符串 '0101111'。
可數性
在我們證明並非所有函數都是可計算的說法之前，最後一個難題是可數性的概念。 直觀地說，我們的證明將表明存在更多的語言； 也就是說，問題多於解決這些問題的可能程序。 這是有效的，因為字符串是否屬於一種語言（是/否）的問題本身就是一個問題。
更準確地說，我們的證明聲稱可能的程序集是可數無限的，而字母表上的語言集是不可數無限的。
在這一點上，你可能會想，“無限本身就是一個很奇怪的想法； 現在我要對付他們兩個！”
好吧，這還不錯。 可數無限集是可以枚舉的。 可以說這是第一個元素，這是第二個元素，依此類推，最終為集合的每個元素分配一個數字。 以偶數集為例。 我們可以說 2 是第一個，4 是第二個，6 是第三個，依此類推。 這樣的集合是可數無限或可數的。
但是，對於某些集合，例如實數，您有多聰明並不重要。 根本沒有枚舉。 這些集合是不可數無限或不可數的。
可數很多程序
首先，我們要證明計算機程序集是可數的。 出於我們的目的，我們通過觀察有限字母表上所有字符串的集合是可數的來做到這一點。 這是有效的，因為計算機程序本身就是有限字符串。
證明很簡單，我們在這裡不詳細介紹。 關鍵的一點是，計算機程序的數量與自然數一樣多。
重申：
任何字母表上的所有字符串的集合（例如，所有計算機程序的集合）都是可數的。
無數種語言
鑑於這個結論，這些字符串的子集呢？ 換一種方式問，所有語言的集合呢？ 事實證明，這個集合是不可數的。
任何字母表上的所有語言的集合都是不可數的。
再一次，我們不在這裡討論證明。
結果
儘管它們可能不會立即顯現出來，但語言的不可數性和所有計算機程序的集合的可數性的後果是深遠的。
為什麼？
假設A是 ASCII 字符集； ASCII 字符只是編寫計算機程序所需的字符。 我們可以看到，表示 JavaScript 程序的字符串集是A*的子集（這裡，* 是 Kleene 星號運算符）。 JavaScript 的選擇是任意的。 由於這組程序是可數集的子集，因此我們認為 JavaScript 程序集是可數的。
此外，讓我們考慮對於任何語言L ，我們可以定義一些函數f ，如果某個字符串x在L中，則其值為 1，否則為 0。 所有這些功能都是不同的。 因為與所有語言的集合有 1:1 的對應關係，並且因為所有語言的集合都是不可數的，所以我們有所有這些函數的集合都是不可數的。
這是深刻的一點：
由於所有有效程序的集合是可數的，但函數的集合不是，那麼肯定有一些函數我們根本無法編寫程序。
我們還不知道這些功能或問題是什麼樣的，但我們知道它們存在。 這是一個令人羞愧的認識，因為存在一些沒有解決方案的問題。 我們認為計算機非常強大和有能力，但有些事情甚至超出了他們的能力範圍。
現在問題變成了，“這些問題是什麼樣的？” 在我們繼續描述這些問題之前，我們必須首先以廣義的方式對計算進行建模。
圖靈機
最早的計算機數學模型之一是由艾倫·圖靈開發的。 這個模型，稱為圖靈機，是一個非常簡單的設備，完全符合我們的可計算性概念。
機器的輸入是輸入已寫入的磁帶。 使用讀/寫頭，機器通過一系列步驟將輸入變為輸出。 在每個步驟中，都會決定是否寫入磁帶以及寫入磁帶的內容以及是否將其向右或向左移動。 這個決定完全基於兩件事：
頭部下方的當前符號，以及
機器的內部狀態，也隨著符號的寫入而更新
而已。
普遍性
1926 年，艾倫·圖靈（Alan Turing）不僅開發了圖靈機，而且在撰寫他的著名論文《論可計算數》時對計算的本質有了許多其他重要見解。 他意識到計算機程序本身可以被視為計算機的輸入。 有了這個觀點，他有了一個美妙的想法，即圖靈機可以模擬或執行該輸入。
雖然我們今天認為這些想法是理所當然的，但在圖靈時代，這種通用機器的想法是讓圖靈開發無法解決的問題的重大突破。
教會圖靈論
在繼續之前，讓我們檢查一個重點：我們知道圖靈機是一種計算模型，但它是否足夠通用？ 為了回答這個問題，我們求助於 Church-Turing Thesis，它證實了以下陳述：
一切可計算的東西都可以用圖靈機計算。
在圖靈開發圖靈機作為計算模型的同時，Alonzo Church 還開發了一種稱為 lambda 演算的計算模型。 這些模型非常強大，因為它們既描述了計算，又以與今天的任何計算機或任何計算機相同的方式來描述計算。 這意味著我們可以使用圖靈機來描述我們尋求的無法解決的問題，因為我們知道我們的發現將適用於過去、現在和以後所有可能的計算機。
可識別性和可判定性
在具體描述一個無法解決的問題之前，我們必須多介紹一點背景知識，即語言識別器和語言決定器的概念。
如果有圖靈機可以識別語言，則該語言是可識別的。
和
如果有一個圖靈機來決定一種語言，那麼它就是可決定的。
要成為一種語言的識別器，圖靈機必須接受該語言中的每個字符串，並且它不能接受任何不是該語言的字符串。 它可能會拒絕或循環此類字符串。 要成為決策者，圖靈機必須始終通過接受或拒絕來停止其輸入。
在這裡，停止輸入的想法至關重要。 事實上，我們看到決策者比識別者更強大。 此外，一個問題是可解決的，或者換句話說，一個函數只有在存在決定函數所描述的語言的圖靈機時才是可判定的。
不確定性
如果您曾經編寫過計算機程序，那麼您肯定知道當程序執行時坐在那兒看著計算機旋轉的感覺。 您不知道程序是否只是花費了很長時間，或者代碼中是否存在某些錯誤導致無限循環。 您甚至可能想知道為什麼編譯器不檢查代碼以查看它在運行時是否會停止或永遠循環。
編譯器沒有這樣的檢查，因為它根本無法完成。 並不是編譯器工程師不夠聰明或缺乏資源； 根本不可能檢查任意計算機程序以確定它是否停止。
我們可以使用圖靈機來證明這一點。 圖靈機可以被描述為字符串，因此它們的數量是可數的。 假設 M 1 、 M 2等構成所有圖靈機的集合。 讓我們定義以下函數：
這裡，<M> 是“M 的字符串編碼”的語法，這個函數表示如果 M i通過接受 M j作為輸入而停止輸出 1，否則輸出 0 的問題。 請注意，M i必須停止（即，成為決策者）。 這是必需的，因為我們希望描述一個不可判定的函數（即，不可解決的問題）。
現在，讓我們也定義一種語言L ，它由不接受自身描述的圖靈機的字符串編碼組成：
例如，某台機器 M 1可能在輸入 <M 1 > 上輸出 0，而另一台機器 M 2可能在輸入 <M 2 > 上輸出 1。 為了證明這種語言是不可判定的，我們詢問決定語言 L 的機器 M L當它自己的描述 <M L > 作為輸入時會做什麼。 有兩種可能：
M L接受 <M L >
要么
M L拒絕 <M L >
如果 M L接受它自己的編碼，那麼這意味著 <M L > 不在語言 L 中； 然而，如果是這樣的話，那麼 M L一開始就不應該接受它的編碼。 另一方面，如果 M L不接受它自己的編碼，那麼 <M L > 在語言 L 中，所以 M L應該接受它的字符串編碼。
在這兩種情況下，我們都有一個悖論，或者用數學術語來說，一個矛盾，證明語言 L 是不可判定的； 因此，我們已經描述了我們的第一個無法解決的問題。
停機問題
雖然我們剛剛描述的問題可能看起來無關緊要，但它可以簡化為具有實際重要性的其他無法解決的問題，最值得注意的是停機問題：
圖靈機在空字符串上停止的編碼語言。
停止問題適用於為什麼編譯器無法從早期檢測到無限循環的問題。 如果我們不能確定一個程序是否在空字符串上終止，那麼我們怎麼可能確定它的執行是否會導致一個無限循環呢？
在這一點上，我們似乎只是為了得出一些簡單的結論而揮手而已； 然而，我們實際上意識到，沒有圖靈機可以判斷計算機程序是否會停止或永遠保持在循環中。 這是實際應用中的一個重要問題，在圖靈機或任何其他類型的計算機上都無法解決。 iPhone 無法解決這個問題。 多核台式機無法解決這個問題。 云無法解決這個問題。 即使有人發明了一台量子計算機，它仍然無法解決停機問題。
概括
在我們對可計算性理論的研究中，我們已經看到有許多函數在任何普通意義上是無法通過計數參數計算的。 我們精確地定義了我們所說的計算的含義，一直追溯到圖靈從他自己的筆和紙經驗中獲得的靈感，從而形式化了圖靈機。 我們已經看到這個模型如何計算任何今天的計算機或未來設想的計算機可以計算的任何東西，並且我們意識到了一類根本無法計算的問題。
儘管如此，可計算性也有不利之處。 僅僅因為我們可以解決問題並不意味著我們可以快速解決它。 畢竟，如果計算機的計算不能在未來數千萬年的太陽對我們產生新星之前完成，那計算機有什麼用呢？
拋開可計算函數和語言，我們現在討論計算複雜性、調查高效計算和著名的 P 與 NP 問題。
複雜
慢與快
計算機科學家認識到各種各樣的問題，我們關心的兩類問題包括計算機可以快速或有效地解決的問題，稱為P和解決方案可以快速驗證但不能快速獲得的問題，稱為NP 。
例如，假設您負責開發在線約會服務的算法，有人提出問題：“每個人都可以約會嗎？” 答案歸結為配對兼容的個人，以便每個人都配對。 事實證明有解決這個問題的有效算法。 這個問題在集合P中。
好吧，如果我們想確定用戶中最大的集團怎麼辦？ 我們所說的集團是指彼此兼容的最大的個人網絡。 當用戶數較少時，這個問題可以很快得到解決。 我們可以很容易地識別出一個有 3 個用戶的集團。 然而，當我們開始尋找更大的集團時，問題變得越來越難以解決。 這個問題在集合NP中。
正式定義
P是在多項式時間內可解決的問題的集合。 也就是說，計算步驟的數量由關於問題大小的多項式函數限制。 我們知道“每個人都可以約會嗎？” 問題，也稱為二分匹配問題，在P中。
NP是在多項式時間內可驗證的問題集。 當然，這包括 P 中的所有問題； 但是，我們不知道這種收容措施是否嚴格。 我們知道可以有效驗證但無法有效解決的問題，但我們不知道問題是否真的難以解決。 集團問題就是這樣一個問題。 我們知道我們可以有效地驗證解決方案，但我們不確定是否可以有效地解決問題。
最後， NP-complete是NP中最難的問題集。 它們被稱為最難的，因為NP中的任何問題都可以有效地轉化為NPC 。 結果，如果有人要找出NPC問題的有效解決方案，那麼整個NP類都將被P吸收。 派系問題也在NPC中。
因此，我們遇到了P與NP的問題。 許多計算機科學家和數學家堅信P和NP不相等。 如果是這樣，其影響將是深遠的。 今天的大部分數字基礎設施都依賴於這樣一個事實，即NP中存在P中沒有的問題。 如果不是這種情況，那麼例如加密方法將在一夜之間崩潰，從而使擁有有效解決NPC問題的人能夠破壞甚至最嚴格的安全協議。
可追踪性的細微之處
對於計算機科學新手來說，匹配問題和集團問題之間的區別可能看起來沒什麼大不了的。 事實上， P中的問題和NP中的問題之間的差異可能非常微妙。 對於在現實世界中設計算法的任何人來說，能夠分辨出差異都很重要。
考慮最短路徑問題。 給定兩個位置，目標是確定它們之間的最短路徑。 iPhone 可以在幾毫秒內完成計算。 這是一個計算上易於處理的問題。
另一方面，考慮旅行推銷員問題，其目標是訪問以起點為終點的可能目的地的子集，同時行駛盡可能短的距離。 這個問題類似於最短路徑問題，但是是 NP 完全的； 它還解釋了為什麼供應鏈物流是一個十億美元的產業。
我們實際上可以更微妙。 我們可以不求最短路徑（P），而是求最長無環路徑。 原來最長路徑問題也是NP完全的。
這種微妙區別還有更多示例，包括識別二分圖與一般圖中的頂點覆蓋或滿足每個子句兩個與三個文字的布爾公式。 關鍵是問題是在 P 還是 NP 並不是很明顯，這就是為什麼運行時間分析是一項關鍵技能。 如果必須設計的算法是針對 P 中的一個問題，那麼我們就知道有一個有效的解決方案。 另一方面，如果問題出在 NP 中，那麼我們有充分的理由反對尋求解決方案，因為算法通常需要很長時間才能解決問題。
概括
在對複雜性的檢查中，我們定義了問題 P 和 NP 的類別。 P 非正式地表示可以由計算機有效解決的問題，而 NP 表示可以有效驗證的問題。
沒有人能夠證明 P 不等於 NP。 這兩類問題是否等價被稱為 P 與 NP 問題，它是當今理論計算機科學中最重要的開放問題，如果不是在所有數學中的話。 事實上，在 2000 年，克萊數學研究所將 P 與 NP 問題命名為數學中七個最重要的開放性問題之一，並懸賞百萬美元懸賞確定該問題的解決方案的證明。
結論
在本文中，我們深入研究了可計算性和復雜性領域，回答了諸如“什麼是計算機？”之類的大問題。 雖然細節可能是壓倒性的，但有一些深刻的要點值得記住：
有些事情根本無法計算，例如停機問題。
有些事情無法有效計算，例如 NPC 中的問題。
比細節更重要的是思考計算和計算問題的方法。 在我們的職業生涯甚至日常生活中，我們可能會遇到從未見過的問題，我們可以使用久經考驗的真實工具和技術來確定最佳行動方案。
進一步閱讀 Toptal 工程博客：
- 如何從頭開始編寫解釋器