Cook-Levin理論
在計算複雜度理論內，Cook–Levin理論或者Cook理論，證明了布尔可满足性问题（SAT）是NP完全問題。換句話說，任何NP裡面的問題可以在多項式時間內，使用圖靈機，將之歸約成「一個布尔方程式是否存在解」這個問題。
這理論一個非常重要的結果是，如果存在一個決定型多項式時間演算法，可以解決SAT的話，則對於所有的NP裡面的問題都存在決定型多項式時間演算法。而且，非常重要的，這對其他的NP完全問題也都成立。
有關以上這個演算法存在與否的問題，又被稱為P/NP問題。而且廣泛認為這是現在的理論電腦科學裡面，最重要的未解問題。Cook–Levin理論是以史提芬·古克和利奥尼德·李文為名。
貢獻
NP-完備的概念是在1960晚期和1970初期，被美國和蘇聯的研究者於同一時期分別建立起來。
在1971年的美國，史提芬·古克發表了他的論文"The complexity of theorem proving procedures"[1]於新成立的ACM Symposium on Theory of Computing內。理查德·卡普接續的論文"Reducibility among combinatorial problems"[2]則藉由提出了二十一個NP-完全問題的列表，讓古克之前的論文重新受到了注意。古克和卡普因為這個成就得到了圖靈獎。
Theodore P. Baker, John Gill，和Robert Solovay於1975年證明了使用諭示機模型解決NP-問題需要指數時間，因此對於NP-完備性的興趣又再次被提高。[3]
在蘇聯，M. Dekhtiar於1969年發表了與Baker，Gill，和Solovay等同的研究。[4]過後利奧尼德·李文的論文"Universal search problems"[5]翻譯過後出版於1973年。不過在更早的幾年之前，這論文的內容就有在演講中提到並且付印過。
李文的研究與古克和卡普些微的不同，在於他考慮的議題專注在搜尋型問題。這類問題不僅僅是找到解答存在與否，還必須要輸出解答。他提出了六個NP-完全的搜尋型問題，並且還附加證明了一個能在最佳時間內解決這問題的演算法。
定義
对于一個決定性問題，如果我們可以使用非決定型圖靈機在多項式時間之內解決它，我们称它在NP內。
一個布爾可滿足性問題的成員（instance）是一個布爾表達式，或者說，一些布爾變數跟布爾邏輯運算符的組合。
对于一個表達式，如果存在某些給予布爾變數真值的方式使得這個表達式的值為真，我们称它可滿足的。
概念
給定任何NP的決定性問題，建立一個可以在多項式時間內解決此問題的非決定型圖靈機。然後，對每個輸入，建立一個布爾表示式，告訴我們這個輸入進去「是否會正確運作，停止，並且回傳答案為真」。那麼，這個表示式就是可滿足的，若且唯若這個機器正確的跑完這個輸入，並且會停止，回答這個輸入是正確的。這樣，問題「這個我們建立的表示式是否可滿足」，與問題「這個圖靈機是否會回傳"真"」就會變成等價的問題。
結果
這個定理的證明展現了任何NP問題都可以在多項式時間內歸約成（另外事實上，只需要對數空間）轉換成一個布爾可滿足性問題。這代表如果布爾可滿足性問題可以用圖靈機在多項式時間內解決，那麼所有NP內的問題都可以在多項式時間內解決，因此複雜度類NP就會等於複雜度類P。
NP-完全的重要性在1972年因為理察·卡普的論文"Reducibility among combinatorial problems"而清楚的表現出來。裡面列出了二十一個有關組合和圖論的問題（卡普的二十一個NP-完全問題），證明裡面的每個均因為其難以解決而惡名昭彰的問題都是NP-完全。[2]
相關資料
- Cook, Stephen. . . 1971: 151–158 [2011-07-20]. （原始内容存档于2020-08-06）.
- Karp, Richard M. . Raymond E. Miller and James W. Thatcher (editors) (编). (PDF). New York: Plenum. 1972: 85–103 [2011-07-20]. ISBN 0306307073. （原始内容存档 (PDF)于2011-06-29）.
- T. P. Baker; J. Gill, R. Solovay. . SIAM Journal on Computing. 1975, 4 (4): 431–442. doi:10.1137/0204037.
- Dekhtiar, M. . Proceedings of the USSR Academy of Sciences. 1969, 14: 1146–1148. （俄文）
- Levin, Leonid. . Problems of Information Transmission (俄語：, Problemy Peredachi Informatsii). 1973, 9 (3): 265–266. （俄文）由Trakhtenbrot, B. A. . Annals of the History of Computing. 1984, 6 (4): 384–400. doi:10.1109/MAHC.1984.10036.