庫克定理

Question

我讀了這本書計算機和難解性 - NP完整性理論指南 Garey和Johnson爲我的算法課程;然而，一年後，在回顧這些材料時，我意識到我從來沒有真正理解庫克定理。

關於這個證明，我理解爲什麼SAT首先被證明是NP（NP-complete的第一個要求），但是我正在努力通過證明在其他NP問題下的「其他」NP完全問題「遺傳」多項式轉換爲SAT。

我在想，如果有人能在一個更淡化的方式解釋，這或許會澄清這部分的附加讀取。

Answer 1

的證明，SAT是NP難的（也就是說，有從每一個NP問題SAT多項式時間減少）是平凡的。我會盡力直觀地瞭解它的工作原理，但我不打算仔細考慮所有的細節。爲此，你可能想查閱一本教科書。

讓我們以任何NP語言L開始。根據定義，L是NP語言的事實意味着對於語言L存在非確定性多項式時間Turing機M.這意味着機器M接受一個字符串w當且僅當w屬於L，並且在此之上M的運行時間是一些多項式p（n）。從L到SAT的減少將表明你可以建立一個命題公式，它基本上模擬了M在某個特定字符串w上的運算。該公式具有M接受w（即w屬於L）的性質，當且僅當所得的命題公式是可滿足的。

根本不清楚是否有可能這樣做。爲了看它是如何工作的，我們將使用標準技術來減少涉及TM的問題。想想字符串w上的M的操作。由於M是一個圖靈機，當我們用w啓動M時，它開始於寫在磁帶上的w（被無限多的空白包圍），在某些狀態下，並且磁帶頭超過w的第一個字符。圖靈機的每一步都會使機器向左或向右移動磁帶頭，替換磁帶頭下的符號，並向左或向右移動磁帶頭。

就在TM的每一步之前，我們可以獲取機器狀態的「快照」。這個快照將在包含磁帶兩端無限多的空白，磁頭位置和TM的當前狀態之後包括磁帶。該「快照」更適當地稱爲機器的瞬時描述或ID。你可以把它想成一個元組（磁帶內容，狀態，位置）。

因爲M是多項式時間NTM，我們知道，它不能大於P多個運行（| W |），當輸入字符串w，其中p是一些多項式跑幾步之遙。因此，當M運行時，計算最多隻有p（| w |）+ 1個瞬時描述，每個步驟一個。因此，您可以將M的任何執行視爲一個接一個地寫出的一系列此ID，如（tape0，state0，position0），（tape1，state1，position1），...，（tapeK，stateK， positionK）。

對這些ID進行兩次觀察。首先，這些ID不能完全是任意的。我們知道第一個ID將會是什麼 - 它將成爲磁帶存放位置的ID，狀態是q ，並且磁帶頭超過字符串w的開頭。因此，根據TM可以爲其第一步所做的每個非確定性選擇，第二個ID將會有幾個可能的選擇。類似地，第三個ID的選擇數量是有限的，因爲該ID必須通過以某個合法的第二個ID開始並且應用TM的一個移動來形成。更一般地說，每個ID必須遵循從先前的ID開始的合法TM移動。第二，請注意，如果M接受w，則存在一些可能的ID鏈，使得鏈中的最後一個ID將處於打開狀態，即機器的接受狀態。相反，如果M不接受w，那麼沒有任何可能的證書鏈將在機器接受狀態下合法結束。

因此，從L到SAT的減少基本上起到了建立一個巨大的命題公式的作用。每個變量對應鏈中某個ID的某個部分（某些特定帶單元的內容，或機器將處於的狀態或磁帶頭的位置）。該公式然後編碼有關ID的規則：第一個ID必須是機器啓動狀態q ，磁帶頭掃描輸入字符串w的第一個字符，每個ID必須跟前一個等等。公式的最後一部分 - 機器必須以接受狀態結束。實際上建立這些公式的所有部分都非常棘手（這就是爲什麼你應該看一本教科書）。然而，最終的結果是，如果公式是可以滿足的，那麼有一系列ID表明M接受w（所以w在L（M）中），如果它不可滿足，那麼M就無法接受w。

希望這會有所幫助！