fbpx
维基百科

庫克-李文定理

十二月 25, 2023

庫克-李文定理（英語：Cook–Levin theorem）或者庫克定理（英語：Cook's theorem）是有关計算複雜度理論的一个定理。它證明了布尔可满足性问题（SAT问题）是NP完全問題。即：

  1. 「一個布尔方程式是否存在解」这个问题本身是一个NP問題；
  2. 任何其他NP问题都可以在多項式時間內被一决定型圖靈機歸約成這個問題。

庫克-李文定理是以史蒂芬·库克和利奥尼德·李文（英语：Leonid Levin）為名。

這定理一個非常重要的推论为：如果SAT问题可在多项式时间内被一确定型演算法解决，則「所有的」NP問題都存在可在多项式时间内解决之的确定型演算法。因此，有關以上這個演算法存在與否的問題等价于P/NP問題——现代的理論電腦科學中最重要的未解問題之一。

定義 编辑

对于一個決定性問題，如果我們可以使用非決定型圖靈機在多項式時間之內解決它，我们称它「在NP內」。

一個「布爾可滿足性問題的成員（instance）」是一個布爾表達式，或者說，一些布爾變數跟布爾邏輯運算符的組合。

对于一個表達式，如果存在某些給予布爾變數真值的方式使得這個表達式的值為真，我们称它「可滿足的」。

概念 编辑

給定任何NP的決定性問題，建立一個可以在多項式時間內解決此問題的非決定型圖靈機。然後，對每個輸入，建立一個布爾表示式，告訴我們這個輸入進去「是否會正確運作，停止，並且回傳答案為真」。那麼，這個表示式就是可滿足的，若且唯若這個機器正確的跑完這個輸入，並且會停止，回答這個輸入是正確的。這樣，問題「這個我們建立的表示式是否可滿足」，與問題「這個圖靈機是否會回傳"真"」就會變成等價的問題。

結果 编辑

這個定理的證明展現了任何NP問題都可以在多項式時間內歸約成（另外事實上，只需要對數空間）轉換成一個布爾可滿足性問題。這代表如果布爾可滿足性問題可以用圖靈機在多項式時間內解決，那麼所有NP內的問題都可以在多項式時間內解決，因此複雜度類NP就會等於複雜度類P。

NP完全的重要性在1972年因為理察·卡普的論文《組合問題之間的可還原性》而清楚的表現出來。裡面列出了二十一個有關組合和圖論的問題（卡普的二十一個NP-完全問題），證明裡面的每個均因為其難以解決而惡名昭彰的問題都是NP完全。[1]

貢獻 编辑

NP完全的概念是在1960年代晚期和1970年代初期，被北美和蘇聯的研究者於同一時期分別建立起來的。在1971年的美國，史蒂芬·库克發表了他的論文《定理證明程式的複雜性》[2]於新成立的ACM計算理論研討會（英语：Symposium on Theory of Computing）內。理查德·卡普接續的論文《組合問題之間的可還原性》[1]則藉由提出了二十一個NP-完全問題的列表，讓庫克之前的論文重新受到了注意。庫克和卡普因為這個成就得到了圖靈獎。

西奧多·P·貝克（Theodore P. Baker）、約翰·吉爾（John Gill）和羅伯特·M·索洛維（英语：Robert M. Solovay）於1975年證明了使用諭示機模型解決NP-問題需要指數時間，因此對於NP-完備性的興趣又再次被提高。[3]

在蘇聯，德赫蒂亞（M. Dekhtiar）於1969年發表了與貝克、吉爾和索洛維等同的研究。[4]過後利奥尼德·李文（英语：Leonid Levin）的論文《通用搜尋型問題》[5]翻譯過後出版於1973年。不過在更早的幾年之前，這論文的內容就有在演講中提到並且付印過。

李文的研究與庫克和卡普些微的不同，在於他考慮的議題專注在搜尋型問題。這類問題不僅僅是找到解答存在與否，還必須要輸出解答。他提出了六個NP-完全的搜尋型問題，並且還附加證明了一個能在最佳時間內解決這問題的演算法。

相關資料 编辑

  1. ^ 1.0 1.1 Karp, 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>标签用不同内容定义了多次
  2. ^ 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）. 
  3. ^ 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. 
  4. ^ 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.  （俄文）
  5. ^ 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. 

十二月 25, 2023
庫克, 李文定理, 英語, cook, levin, theorem, 或者庫克定理, 英語, cook, theorem, 是有关計算複雜度理論的一个定理, 它證明了布尔可满足性问题, sat问题, 是np完全問題, 一個布尔方程式是否存在解, 这个问题本身是一个np問題, 任何其他np问题都可以在多項式時間內被一决定型圖靈機歸約成這個問題, 是以史蒂芬, 库克和利奥尼德, 李文, 英语, leonid, levin, 為名, 這定理一個非常重要的推论为, 如果sat问题可在多项式时间内被一确定型演算法解决, 所. 庫克 李文定理 英語 Cook Levin theorem 或者庫克定理 英語 Cook s theorem 是有关計算複雜度理論的一个定理 它證明了布尔可满足性问题 SAT问题 是NP完全問題 即 一個布尔方程式是否存在解 这个问题本身是一个NP問題 任何其他NP问题都可以在多項式時間內被一决定型圖靈機歸約成這個問題 庫克 李文定理是以史蒂芬 库克和利奥尼德 李文 英语 Leonid Levin 為名 這定理一個非常重要的推论为 如果SAT问题可在多项式时间内被一确定型演算法解决 則 所有的 NP問題都存在可在多项式时间内解决之的确定型演算法 因此 有關以上這個演算法存在與否的問題等价于P NP問題 现代的理論電腦科學中最重要的未解問題之一 目录 1 定義 2 概念 3 結果 4 貢獻 5 相關資料定義 编辑对于一個決定性問題 如果我們可以使用非決定型圖靈機在多項式時間之內解決它 我们称它 在NP內 一個 布爾可滿足性問題的成員 instance 是一個布爾表達式 或者說 一些布爾變數跟布爾邏輯運算符的組合 对于一個表達式 如果存在某些給予布爾變數真值的方式使得這個表達式的值為真 我们称它 可滿足的 概念 编辑給定任何NP的決定性問題 建立一個可以在多項式時間內解決此問題的非決定型圖靈機 然後 對每個輸入 建立一個布爾表示式 告訴我們這個輸入進去 是否會正確運作 停止 並且回傳答案為真 那麼 這個表示式就是可滿足的 若且唯若這個機器正確的跑完這個輸入 並且會停止 回答這個輸入是正確的 這樣 問題 這個我們建立的表示式是否可滿足 與問題 這個圖靈機是否會回傳 真 就會變成等價的問題 結果 编辑這個定理的證明展現了任何NP問題都可以在多項式時間內歸約成 另外事實上 只需要對數空間 轉換成一個布爾可滿足性問題 這代表如果布爾可滿足性問題可以用圖靈機在多項式時間內解決 那麼所有NP內的問題都可以在多項式時間內解決 因此複雜度類NP就會等於複雜度類P NP完全的重要性在1972年因為理察 卡普的論文 組合問題之間的可還原性 而清楚的表現出來 裡面列出了二十一個有關組合和圖論的問題 卡普的二十一個NP 完全問題 證明裡面的每個均因為其難以解決而惡名昭彰的問題都是NP完全 1 貢獻 编辑NP完全的概念是在1960年代晚期和1970年代初期 被北美和蘇聯的研究者於同一時期分別建立起來的 在1971年的美國 史蒂芬 库克發表了他的論文 定理證明程式的複雜性 2 於新成立的ACM計算理論研討會 英语 Symposium on Theory of Computing 內 理查德 卡普接續的論文 組合問題之間的可還原性 1 則藉由提出了二十一個NP 完全問題的列表 讓庫克之前的論文重新受到了注意 庫克和卡普因為這個成就得到了圖靈獎 西奧多 P 貝克 Theodore P Baker 約翰 吉爾 John Gill 和羅伯特 M 索洛維 英语 Robert M Solovay 於1975年證明了使用諭示機模型解決NP 問題需要指數時間 因此對於NP 完備性的興趣又再次被提高 3 在蘇聯 德赫蒂亞 M Dekhtiar 於1969年發表了與貝克 吉爾和索洛維等同的研究 4 過後利奥尼德 李文 英语 Leonid Levin 的論文 通用搜尋型問題 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 庫克 李文定理 amp oldid 80203633, 维基百科，wiki，书籍，书籍，图书馆，

文章

，阅读，下载，免费，免费下载，mp3，视频，mp4，3gp， jpg，jpeg，gif，png，图片，音乐，歌曲，电影，书籍，游戏，游戏。