Cook-Levin理论

Cook–Levin理论或者Cook理论是有关计算复杂度理论的一个定理。它证明了布尔可满足性问题（SAT 问题）是NP完全问题。即：

  1. “一个布尔方程式是否存在解”这个问题本身是一个NP问题；
  2. 任何其他NP问题都可以在多项式时间内被一决定型图灵机归约成这个问题。

Cook–Levin理论是以史提芬·古克和利奥尼德·李文为名。

这理论一个非常重要的推论为：如果SAT问题可在多项式时间内被一确定型算法解决，则所有的NP问题都存在可在多项式时间内解决之的确定型算法。因此，有关以上这个算法存在与否的问题等价于P/NP问题——现代的理论计算机科学中最重要的未解问题之一。

定义

对于一个决定性问题，如果我们可以使用非决定型图灵机在多项式时间之内解决它，我们称它在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. ^ 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.