跳转到内容

库克-李文定理

维基百科,自由的百科全书

库克-李文定理(英语: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) (编). Complexity of Computer Computations (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.