Cook-Levin定理，也稱為Cook定理，表明布爾可滿足性問題是NP完全的。 也就是說，NP中的任何問題都可以通過確定性圖靈機在多項式時間內減少到確定布爾公式是否可滿足的問題。
該定理以史蒂芬庫克和列昂尼德萊文命名。
基本介紹
- 中文名：Cook-Levin理論
- 外文名：Cook-Levin theory
- 別名：Cook定理
定義,理念,後果,
定義
如果可以在多項式時間內通過非確定性算法求解，則決策問題在NP中。布爾可滿足性問題的一個實例是布爾表達式，它使用布爾運算符組合布爾變數。如果將某些真值賦值給整個表達式為真的變數，則表達式是可以滿足的。
理念
給定NP中的任何決策問題，構造一個在多項式時間內解決它的非確定性機器。 然後，對於該機器的每個輸入，構建一個布爾表達式，表示輸入傳遞給機器，機器正確運行，機器停止並回答“是”。 然後，若且唯若機器能夠正確運行並回答“是”時，才能滿足表達式，因此構造表達式的可滿足性等同於詢問機器是否將回答“是”。
後果
證明表明NP中的任何問題都可以在多項式時間（實際上，對數空間足夠）中減少到布爾可滿足性問題的實例。這意味著如果布爾可滿足性問題可以通過確定性圖靈機在多項式時間內求解，則NP中的所有問題都可以在多項式時間內求解，因此複雜度類NP將等於複雜度類P。
1972年Richard Karp的一篇具有里程碑意義的論文“組合問題中的可還原性”的出版物清楚地表明了NP完全性的重要性，其中他表明21個不同的組合和圖論理論問題，每個都因其難以處理而臭名昭著，是NP完全的。
卡普通過減少另一個問題（已經證明是NP完全的）來證明他的每個問題都是NP完全的。例如，他通過展示如何將（在多項式時間內）任何SAT實例減少到（以多項式時間為單位）來顯示問題3SAT（連線正規形式的表達式的布爾可滿足性問題，正好有三個變數或每個子句的變數否定）。 3SAT的等效實例。 （首先修改Cook-Levin定理的證明，使得得到的公式為合取範式，然後將新變數引入具有3個以上原子的split子句。例如，子句（A∨B∨C∨ D）可以用子句的結合代替（A∨B∨Z）∧（¬Z∨C∨D），其中Z是一個新的變數，不會在表達式的任何其他地方使用。少於3個原子的子句可以填充;例如，A可以用（A∨A∨A）代替，（A∨B）可以用（A∨B∨B）代替。
Garey和Johnson在他們的著作“計算機與難以理解：NP完全性理論指南”[6]中提出了300多個NP完全問題，並且仍然發現新問題屬於複雜性類別。
儘管SAT的許多實際實例可以通過啟發式方法來解決，但是對於SAT是否存在確定性多項式時間算法（以及因此所有其他NP完全問題）的問題仍然是一個著名的未解決的問題，儘管經過數十年的努力，複雜性理論家，數學邏輯學家和其他人。有關更多詳細信息，請參閱文章P與NP問題。
