Loading AI tools
库克-李文定理（英语：Cook–Levin theorem）或者库克定理（英语：Cook's theorem）是有关计算复杂度理论的一个定理。它证明了布尔可满足性问题（SAT问题）是NP完全问题。即：
库克-李文定理是以史蒂芬·库克和利奥尼德·李文为名。
这定理一个非常重要的推论为：如果SAT问题可在多项式时间内被一确定型算法解决，则“所有的”NP问题都存在可在多项式时间内解决之的确定型算法。因此，有关以上这个算法存在与否的问题等价于P/NP问题——现代的理论电脑科学中最重要的未解问题之一。
对于一个决定性问题，如果我们可以使用非决定型图灵机在多项式时间之内解决它，我们称它“在NP内”。
一个“布尔可满足性问题的成员（instance）”是一个布尔表达式，或者说，一些布尔变数跟布尔逻辑运算符的组合。
对于一个表达式，如果存在某些给予布尔变数真值的方式使得这个表达式的值为真，我们称它“可满足的”。
给定任何NP的决定性问题，建立一个可以在多项式时间内解决此问题的非决定型图灵机。然后，对每个输入，建立一个布尔表示式，告诉我们这个输入进去“是否会正确运作，停止，并且回传答案为真”。那么，这个表示式就是可满足的，当且仅当这个机器正确的跑完这个输入，并且会停止，回答这个输入是正确的。这样，问题“这个我们建立的表示式是否可满足”，与问题“这个图灵机是否会回传"真"”就会变成等价的问题。
这个定理的证明展现了任何NP问题都可以在多项式时间内归约成（另外事实上，只需要对数空间）转换成一个布尔可满足性问题。这代表如果布尔可满足性问题可以用图灵机在多项式时间内解决，那么所有NP内的问题都可以在多项式时间内解决，因此复杂度类NP就会等于复杂度类P。
NP完全的重要性在1972年因为理察·卡普的论文《组合问题之间的可还原性》而清楚的表现出来。里面列出了二十一个有关组合和图论的问题（卡普的二十一个NP-完全问题），证明里面的每个均因为其难以解决而恶名昭彰的问题都是NP完全。[1]
NP完全的概念是在1960年代晚期和1970年代初期，被北美和苏联的研究者于同一时期分别建立起来的。在1971年的美国，史蒂芬·库克发表了他的论文《定理证明程式的复杂性》[2]于新成立的ACM计算理论研讨会内。理查德·卡普接续的论文《组合问题之间的可还原性》[1]则借由提出了二十一个NP-完全问题的列表，让库克之前的论文重新受到了注意。库克和卡普因为这个成就得到了图灵奖。
西奥多·P·贝克（Theodore P. Baker）、约翰·吉尔（John Gill）和罗伯特·M·索洛维于1975年证明了使用谕示机模型解决NP-问题需要指数时间，因此对于NP-完备性的兴趣又再次被提高。[3]
在苏联，德赫蒂亚（M. Dekhtiar）于1969年发表了与贝克、吉尔和索洛维等同的研究。[4]过后利奥尼德·李文的论文《通用搜寻型问题》[5]翻译过后出版于1973年。不过在更早的几年之前，这论文的内容就有在演讲中提到并且付印过。
李文的研究与库克和卡普些微的不同，在于他考虑的议题专注在搜寻型问题。这类问题不仅仅是找到解答存在与否，还必须要输出解答。他提出了六个NP-完全的搜寻型问题，并且还附加证明了一个能在最佳时间内解决这问题的算法。
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
