跳轉到

09.2-NPComplete問題

NP-Complete 問題的詳細解釋#

NP-Complete 問題是一類在計算複雜度理論中具有特殊地位的問題。具體來說，這些問題是 NP 類問題中的“最難”的問題。NP-Complete 的定義由兩個條件組成：

  1. 屬於 NP 類問題：即該問題的解可以在多項式時間內驗證，也就是說，給定一個解，我們可以在多項式時間內檢查它是否正確。

  2. NP 完備性：任何其他 NP 類問題都可以在多項式時間內歸約到這個問題。換句話說，這些問題是 NP 類中最具代表性和最難解的問題，任何一個 NP 問題都可以通過某種變換被轉化為一個 NP-Complete 問題。

為什麼 SAT 是一個 NP-Complete 問題？#

SAT (Satisfiability Problem) 是判定一個布爾公式是否可以滿足的問題。具體來說，給定一個布爾公式，問題是要確定是否存在一組變量賦值，使得該公式的值為 True。

SAT 問題是 NP 類問題的代表之一，因為： - 驗證解的多項式時間性：給定一個布爾公式的解（即一組變量的賦值），我們可以在多項式時間內檢查該賦值是否使得公式成立。如果公式成立，則該解是正確的。

然而，SAT 問題最重要的性質在於它是 NP-Complete 問題的第一個已知例子，這意味著它同時滿足了以下條件： - 它屬於 NP 類（其解可以在多項式時間內驗證）。 - 任何其他的 NP 類問題都可以多項式時間內被歸約到 SAT 問題。

這也表明，如果我們能夠找到 SAT 問題的一個多項式時間算法，那麼所有 NP 類問題都將能夠在多項式時間內解決，即 P = NP。

Steven Cook 如何證明 SAT 是 NP-Complete 問題#

Steven Cook 在 1971 年發表了他的著名定理，證明了 SAT 問題是 NP-Complete 問題，這一發現被稱為 Cook 定理。Cook 的證明方法涉及到將所有 NP 類問題歸約（reduction）到 SAT 問題的過程。具體來說，Cook 的證明包含兩個主要部分：

1. SAT 屬於 NP 類#

首先，Cook 證明了 SAT 屬於 NP 類問題，即給定一組變量賦值，我們可以在多項式時間內驗證該賦值是否使得布爾公式為真。這一點是相對直觀的：只需要對所有變量賦值，並檢查公式的真值。

2. 所有 NP 問題可歸約到 SAT 問題#

這是 Cook 定理的核心部分。Cook 需要證明，對於任意的 NP 問題，都可以將其轉換為 SAT 問題。換句話說，任何 NP 類問題都可以在多項式時間內轉化為 SAT 問題的實例。

Cook 的證明使用了 多項式時間歸約（polynomial-time reduction） 的概念。具體步驟是： - 假設有一個任意的 NP 類問題 A，並且有一個決策算法，能夠在多項式時間內驗證問題 A 的解是否正確。 - Cook 展示了如何將這個問題 A 的每一個可能的解，通過一個多項式時間的過程轉化為 SAT 問題。 - 這樣，我們就可以將任意的 NP 問題 A 轉化為 SAT 問題，並且這個轉化過程不會超過多項式時間。

具體來說，Cook 證明了每個 NP 問題都可以被轉化為一個布爾公式，這個公式的滿足性問題就是 SAT 問題。

Cook 的歸約過程：#

  • 他首先構建了一個 非決定性圖靈機，並將這個圖靈機的運行過程轉化為一個布爾公式。
  • 然後，這個公式代表了圖靈機計算過程中的所有狀態和過渡，並且它的滿足性問題就對應於原來的 NP 問題的解。
  • Cook 的關鍵觀察是：對於圖靈機的每一個可能的運行步驟，都可以用一個布爾變量來表示，這樣就能將整個圖靈機的運行過程轉化為一個布爾公式。

為什麼這個證明重要？#

Cook 的證明有以下幾個關鍵的意義： 1. 首次證明了 SAT 是 NP-Complete：這個證明揭示了 SAT 問題的特殊地位，使其成為 NP-Complete 類問題的代表。 2. 開創了 NP-Complete 理論：Cook 的定理啟發了後來更多 NP-Complete 問題的發現。例如，許多實際中的困難問題（如旅行商問題、背包問題等）都被證明是 NP-Complete 問題。 3. 多項式時間歸約的概念：Cook 證明的方法引入了多項式時間歸約的概念，即將一個問題轉化為另一個問題，並且這個轉化過程必須在多項式時間內完成。

小結#

  • SAT 問題是 NP-Complete 問題，意味著它是 NP 類問題中最難的一類問題。如果能在多項式時間內解決 SAT 問題，那麼所有 NP 問題都能在多項式時間內解決，這將導致 P = NP 的結論。
  • Steven Cook 在 1971 年證明了 SAT 問題是 NP-Complete，並且使用多項式時間歸約將任意的 NP 問題轉化為 SAT 問題，這一發現是計算機科學中最為深刻的結果之一，並對理論計算機科學產生了深遠的影響。