庫克定理(Cook theorem)第一個NP完全問題.是庫克(Cook , S. A.)於1971年證明的一個結果。
:可滿足性問題SAT是NP完全的.這是注意到，若語言L E NP，並且SAT多項式可化歸到L，則L也是NP完全的.可見第一個NP完全性問題有著特別重要的意義.
庫克定理
相關詞條
- 庫克定理
庫克定理(Cook theorem)第一個NP完全問題.是庫克(Cook , S. A.)於1971年證明的一個結果。...
- 史蒂芬·庫克(多倫多大學計算複雜理論教授)
史蒂芬·A·庫克(Stephen A. Cook,1939年12月14日-),1961年從University of Michigan獲得其學士學位,於1962年和1966年從哈佛大學分別獲得其碩士與博士學位。1966...
- Cook-Levin理論
Cook-Levin定理,也稱為Cook定理,表明布爾可滿足性問題是NP完全的。 也就是說,NP中的任何問題都可以通過確定性圖靈機在多項式時間內減少到確定布爾公式是否可滿足的...
- 理查森定理
1915年裡查森和庫克(H.L.Cooke)合作,改進實驗方法,最終確認了理論的正確。理查森定理逆過程 編輯 另一途徑是其逆過程。里查森提出,如果電子束是從外部流進導體,則...
- Steven A. Cook
史蒂芬·庫克(Stephen Arthur. Cook)1961年從University of Michigan獲得其學士學位,於1962年和1966年從哈佛大學分別獲得其碩士與博士學位。1966年到1970年,Stephen在...
- 計算複雜性理論(理論計算機科學分支學科)
然而1970年代的由史蒂芬·庫克和列昂尼德·列文分別發現的庫克-列文定理,證明了布爾表達式(Boolean formula)的可滿足性問題(SAT問題)是NP完備的。概括的說,他們證明了...
- 語言與機器
圖靈機、圖靈可計算函式、喬姆斯基層次、判定問題與丘奇圖靈機、不可判定性、Mu—遞歸函式、時間複雜性、庫克定理、NP—完全問題、LL(k)文法以及LR(k)文法等問題...
