計算機科學基礎/計算的極限

計算的極限

我們已經研究了一些計算的重要思想，它使我們能夠透過資訊處理來執行驚人的任務。你可能已經產生了這樣的印象：如果我們可以量化資訊並設計算法，我們就可以使用計算來解決任何問題。在本章中，我們將研究有關計算極限的理論。在計算可以為我們做的事情方面，存在理論和實際限制。

圖靈機再探

當我們討論“演算法”的正式定義時，我們引入了圖靈機，它是一個用於計算的數學模型。透過這個模型，我們可以研究計算的本質，包括它可能做的事情。艾倫·圖靈在他的模型機方面對可計算性理論做出了巨大貢獻。他證明了圖靈機與我們能構建的任何計算機一樣強大（圖靈完備性）。如果我們能找到圖靈機無法解決的問題，我們就證明了該問題的解決方案不可計算，即該問題無法透過任何計算機上的計算來解決。

停機問題

1936 年，艾倫·圖靈證明，對於所有可能的程式-輸入對，解決停機問題的通用演算法不存在，即停機問題無法透過計算來解決。更具體地說，停機問題是不可判定的，因為它是回答是或否（決策）問題的最簡單型別的問題：給定一個輸入，程式最終是否會停止（停止）。顯然，實際執行程式並輸入以檢視它是否會停止是不可行的，因為它可能永遠執行，如果程式中存在無限迴圈。這個想法是分析一個給定輸入的程式，以確定它是否會停止。

艾倫·圖靈透過一種稱為反證法的證明技術證明了停機問題是不可判定的。回顧維基百科上的一些示例證明將非常有幫助。另一個經典的例子是數論中歐幾里得定理的證明，該定理斷言存在無限多個素數。所有反證法都從一個假設開始，即我們試圖證明的命題是錯誤的，遵循一系列邏輯上有效的步驟，並得出明顯錯誤或矛盾的結論，這也是錯誤的，因為一個命題可以是真或假，但不能同時是兩者。

如果我們假設停機問題是可判定的/可解決的，那麼我們應該能夠設計一個演算法並將其實現為一個程式，為我們解決這個問題。該程式應將程式和程式的輸入作為輸入引數，並返回答案——程式在輸入上是否會停止。這樣的程式可能聽起來很奇怪，因為它將程式作為輸入，但我們已經看到過這樣的程式，例如，Snap! 中的高階函式塊將一個塊（程式）作為輸入，一個直譯器程式將程式的原始碼作為資料並執行程式。程式是資料，兩者之間沒有本質區別。以下證明表明，一個回答停機問題的程式是不存在的。

假設存在這樣一個程式 A。A(P, D) -> 程式 P 在輸入資料 D 上是否停止。
我們可以建立另一個程式 B，它將程式作為輸入。在程式 B 內部，我們可以呼叫程式 A，將給定的輸入作為輸入，以確定輸入程式是否會在自身作為輸入資料時停止，如果答案為否（不會停止），我們停止（返回），如果答案為是（會停止），則無限迴圈。

 B(P):
   if A(P, P) = yes 
     infinite loop
   else
     return

如果我們將程式 B 本身作為輸入提供給它會發生什麼？或者更簡單地說，程式 B 在自身上是否會停止？該練習有兩個可能的結果：程式 B 在自身上停止或程式 B 在自身作為輸入時永遠執行。實際的結果/結果取決於程式 B 內部呼叫的程式 A 的結果。如果程式 B 在自身上停止，根據程式 B 的設計，它應該永遠執行，因為程式 A 將程式 B 作為輸入，應該執行無限迴圈。另一方面，如果程式 B 在自身上不會停止，那麼程式 B 接收自身作為輸入的輸出應該立即返回。無論哪種方式都是一個矛盾。
到目前為止，我們做了一個假設，遵循了一系列邏輯上合理的步驟，最後得出了矛盾。哪裡錯了？矛盾不可能為真，因為它們在邏輯上是不可能的。這些步驟在邏輯上是合理的，唯一可能出錯的部分是假設。因此，假設不可能為真，即停機問題是不可判定的。

這裡有一個 YouTube 影片說明了證明：https://www.youtube.com/watch?v=92WHN-pAFCs

難以解決的問題

停機問題之所以困難，是因為它原則上甚至無法用演算法解決。還有其他一些難題，原則上是可以解決的，但實際上它們幾乎不可能解決。如你所見，我們可以根據最佳已知演算法的效能對問題進行分類。如果一個問題可以使用快速演算法解決，那麼這個問題很簡單，因為我們可以使用計算機快速解決它。相反，如果我們知道的最佳演算法需要很長時間來解決問題，那麼它就很難，因為計算機無法快速解決它。

使用演算法複雜性理論，我們可以根據演算法的複雜性將每個演算法歸入特定的類別。如果一個類別的 Big-O 表示法只包含多項式項，那麼可以使用該類別中的演算法解決的問題稱為 P 問題（存在多項式時間解），例如 $O(1)$ 、 $log_{2}(N)$ $O(N)$ 和 $O(N^{2})$ 。P 問題是計算機容易解決的問題。在沒有多項式時間解的問題中，有一些問題，如果我們可以猜測出解，就可以在多項式時間內驗證它。例如，整數分解（或素數分解）問題沒有已知的

我們將解決時間過長的問題統稱為棘手問題，包括最佳演算法時間複雜度為指數時間 ( $O(2^{N})$ ) 的問題，或者那些具有多項式時間解但指數過大的問題，例如 $O(N^{15})$ 。

如果一個問題的最佳演算法解的時間複雜度為 $O(2^{N})$ ，當 $N=100$ 並且一臺計算機每秒執行 $10^{12}$ 次運算，那麼這臺計算機需要 $4\times 10^{10}$ 年（相當於宇宙年齡）才能解決這個問題。

P 與 NP

顯然，P 是 NP 的子集，因為 NP 的定義僅限於多項式時間驗證答案，而在多項式時間內解決問題（P）當然符合這一條件。P 是否是 NP 的真子集，換句話說， $P=NP$ 是否成立，仍然是計算機科學領域的一個開放性問題。沒有人知道答案。如果你能解決這個問題，你就可以獲得一百萬美元的獎金，這是千年大獎難題之一。

為了解決 P 與 NP 問題，理論計算機科學家定義了另一個類別，稱為 NP 完全問題。這三個類別的關係如下圖所示。

所有屬於該類別的問題都是 NP 問題，它們共享一個特殊屬性 - 所有其他 NP 完全問題都可以透過多項式時間進行轉換/歸約到每個 NP 完全問題。由於 NP 完備性的性質，如果我們能解決該類別中的任何一個問題，我們就能證明所有 NP 問題都可以在多項式時間內得到解決，即 $P=NP$ 。我們可以取任何 NP 問題，將其轉化為已經解決的 NP 完全問題，並在多項式時間內解決該問題。總的時間仍然是多項式時間，因為多項式時間加上多項式時間仍然是多項式時間。已經發現了數千個 NP 完全問題，但沒有一個得到解決。從某種意義上說，NP 完全問題是最難解決的已知問題。

大多數計算機科學家相信 $P\neq NP$ ，因為如果 P = NP，那麼其後果將非常重大。“創造性飛躍”將消失，因為解決問題將變得像識別正確答案一樣容易。大多數加密演算法都是計算安全的，因為破解它們是 NP 問題 - 沒有已知的多項式時間高效解決方案。如果 $P=NP$ ，那麼所有的加密都會被破解。

計算機科學中還有其他未解決的問題。你可以在 https://en.wikipedia.org/wiki/List_of_unsolved_problems_in_computer_science 中找到這些問題的列表。