NP-完全的重要性在1972年因為理察·卡普的論文"Reducibility among combinatorial problems"而清楚的表現出來。裡面列出了二十一個有關組合和圖論的問題（卡普的二十一個NP-完全問題），證明裡面的每個均因為其難以解決而惡名昭彰的問題都是NP-完全。[1]
貢獻
NP-完備的概念是在1960晚期和1970初期，被北美和蘇聯的研究者於同一時期分別建立起來的。在1971年的美國，史提芬·古克發表了他的論文"The complexity of theorem proving procedures"[2]於新成立的ACM Symposium on Theory of Computing內。理查德·卡普接續的論文"Reducibility among combinatorial problems"[1]則藉由提出了二十一個NP-完全問題的列表，讓古克之前的論文重新受到了注意。古克和卡普因為這個成就得到了圖靈獎。
Theodore P. Baker, John Gill，和Robert Solovay於1975年證明了使用諭示機模型解決NP-問題需要指數時間，因此對於NP-完備性的興趣又再次被提高。[3]
^ 1.01.1Karp, Richard M. Reducibility Among Combinatorial Problems. Raymond E. Miller and James W. Thatcher (editors) (编). (PDF). New York: Plenum. 1972: 85–103 [2011-07-20]. ISBN 0306307073. （原始内容 (PDF)存档于2011-06-29）.引用错误：带有name属性“Karp”的<ref>标签用不同内容定义了多次
^Cook, Stephen. The complexity of theorem proving procedures. Proceedings of the Third Annual ACM Symposium on Theory of Computing. 1971: 151–158 [2011-07-20]. （原始内容于2020-08-06）.
^T. P. Baker; J. Gill, R. Solovay. Relativizations of the P = NP question. SIAM Journal on Computing. 1975, 4 (4): 431–442. doi:10.1137/0204037.引文使用过时参数coauthors (帮助)
^Dekhtiar, M. On the impossibility of eliminating exhaustive search in computing a function relative to its graph. Proceedings of the USSR Academy of Sciences. 1969, 14: 1146–1148.（俄文）
^Levin, Leonid. Universal search problems (俄語：Универсальные задачи перебора, Universal'nye perebornye zadachi). Problems of Information Transmission (俄語：Проблемы передачи информации, Problemy Peredachi Informatsii). 1973, 9 (3): 265–266.（俄文）由Trakhtenbrot, B. A. A survey of Russian approaches to perebor（brute-force searches）algorithms. Annals of the History of Computing. 1984, 6 (4): 384–400. doi:10.1109/MAHC.1984.10036.
一月 28, 2023
cook, levin理論, cook, levin理論或者cook理論是有关計算複雜度理論的一个定理, 它證明了布尔可满足性问题, 问题, 是np完全問題, 一個布尔方程式是否存在解, 这个问题本身是一个np問題, 任何其他np问题都可以在多項式時間內被一决定型圖靈機歸約成這個問題, cook, levin理論是以史提芬, 古克和利奥尼德, 李文為名, 這理論一個非常重要的推论为, 如果sat问题可在多项式时间内被一确定型演算法解决, 則所有的np問題都存在可在多项式时间内解决之的确定型演算法, 因此, 有關以上. Cook Levin理論或者Cook理論是有关計算複雜度理論的一个定理 它證明了布尔可满足性问题 SAT 问题 是NP完全問題 即 一個布尔方程式是否存在解 这个问题本身是一个NP問題 任何其他NP问题都可以在多項式時間內被一决定型圖靈機歸約成這個問題 Cook Levin理論是以史提芬 古克和利奥尼德 李文為名 這理論一個非常重要的推论为 如果SAT问题可在多项式时间内被一确定型演算法解决 則所有的NP問題都存在可在多项式时间内解决之的确定型演算法 因此 有關以上這個演算法存在與否的問題等价于P NP問題 现代的理論電腦科學中最重要的未解問題之一 目录 1 定義 2 概念 3 結果 4 貢獻 5 相關資料定義 编辑对于一個決定性問題 如果我們可以使用非決定型圖靈機在多項式時間之內解決它 我们称它在NP內 一個布爾可滿足性問題的成員 instance 是一個布爾表達式 或者說 一些布爾變數跟布爾邏輯運算符的組合 对于一個表達式 如果存在某些給予布爾變數真值的方式使得這個表達式的值為真 我们称它可滿足的 概念 编辑給定任何NP的決定性問題 建立一個可以在多項式時間內解決此問題的非決定型圖靈機 然後 對每個輸入 建立一個布爾表示式 告訴我們這個輸入進去 是否會正確運作 停止 並且回傳答案為真 那麼 這個表示式就是可滿足的 若且唯若這個機器正確的跑完這個輸入 並且會停止 回答這個輸入是正確的 這樣 問題 這個我們建立的表示式是否可滿足 與問題 這個圖靈機是否會回傳 真 就會變成等價的問題 結果 编辑這個定理的證明展現了任何NP問題都可以在多項式時間內歸約成 另外事實上 只需要對數空間 轉換成一個布爾可滿足性問題 這代表如果布爾可滿足性問題可以用圖靈機在多項式時間內解決 那麼所有NP內的問題都可以在多項式時間內解決 因此複雜度類NP就會等於複雜度類P NP 完全的重要性在1972年因為理察 卡普的論文 Reducibility among combinatorial problems 而清楚的表現出來 裡面列出了二十一個有關組合和圖論的問題 卡普的二十一個NP 完全問題 證明裡面的每個均因為其難以解決而惡名昭彰的問題都是NP 完全 1 貢獻 编辑NP 完備的概念是在1960晚期和1970初期 被北美和蘇聯的研究者於同一時期分別建立起來的 在1971年的美國 史提芬 古克發表了他的論文 The complexity of theorem proving procedures 2 於新成立的ACM Symposium on Theory of Computing內 理查德 卡普接續的論文 Reducibility among combinatorial problems 1 則藉由提出了二十一個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 完全的搜尋型問題 並且還附加證明了一個能在最佳時間內解決這問題的演算法 相關資料 编辑 1 0 1 1 Karp Richard M Reducibility Among Combinatorial Problems Raymond E Miller and James W Thatcher editors 编 Complexity of Computer Computations PDF New York Plenum 1972 85 103 2011 07 20 ISBN 0306307073 原始内容 PDF 存档于2011 06 29 引用错误 带有name属性 Karp 的 lt ref gt 标签用不同内容定义了多次 Cook Stephen The complexity of theorem proving procedures Proceedings of the Third Annual ACM Symposium on Theory of Computing 1971 151 158 2011 07 20 原始内容存档于2020 08 06 T P Baker J Gill R Solovay Relativizations of the P NP question SIAM Journal on Computing 1975 4 4 431 442 doi 10 1137 0204037 引文使用过时参数coauthors 帮助 Dekhtiar M On the impossibility of eliminating exhaustive search in computing a function relative to its graph Proceedings of the USSR Academy of Sciences 1969 14 1146 1148 俄文 Levin Leonid Universal search problems 俄語 Universalnye zadachi perebora Universal nye perebornye zadachi Problems of Information Transmission 俄語 Problemy peredachi informacii Problemy Peredachi Informatsii 1973 9 3 265 266 俄文 由Trakhtenbrot B A A survey of Russian approaches to perebor brute force searches algorithms Annals of the History of Computing 1984 6 4 384 400 doi 10 1109 MAHC 1984 10036 取自 https zh wikipedia org w index php title Cook Levin理論 amp oldid 71581027, 维基百科，wiki，书籍，书籍，图书馆，
