
_START_ARTICLE_
Cook-Levin理論
_START_PARAGRAPH_
在计算复杂度理论内，Cook–Levin理论或者Cook理论，证明了布尔可满足性问题（SAT）是NP完全问题。换句话说，任何NP里面的问题可以在多项式时间内，使用图灵机，将之归约成“一个布林方程式是否存在解”这个问题。_NEWLINE_这理论一个非常重要的结果是，如果存在一个决定型多项式时间算法，可以解决SAT的话，则对于所有的NP里面的问题都存在决定型多项式时间算法。而且，非常重要的，这对其他的NP完全问题也都成立。_NEWLINE_有关以上这个算法存在与否的问题，又被称为P/NP问题。而且广泛认为这是现在的理论计算机科学里面，最重要的未解问题。Cook–Levin理论是以史提芬·古克和利奥尼德·李文为名。
_START_SECTION_
贡献
_START_PARAGRAPH_
NP-完备的概念是在1960晚期和1970初期，被美国和苏联的研究者于同一时期分别建立起来。_NEWLINE_在1971年的美国，史提芬·古克发表了他的论文"The complexity of theorem proving procedures"于新成立的ACM Symposium on Theory of Computing内。理查德·卡普接续的论文"Reducibility among combinatorial problems"则借由提出了二十一个NP-完全问题的列表，让古克之前的论文重新受到了注意。古克和卡普因为这个成就得到了图灵奖。_NEWLINE_Theodore P. Baker, John Gill，和Robert Solovay于1975年证明了使用谕示机模型解决NP-问题需要指数时间，因此对于NP-完备性的兴趣又再次被提高。_NEWLINE_在苏联，M. Dekhtiar于1969年发表了与Baker，Gill，和Solovay等同的研究。过后利奥尼德·李文的论文"Universal search problems"翻译过后出版于1973年。不过在更早的几年之前，这论文的内容就有在演讲中提到并且付印过。_NEWLINE_李文的研究与古克和卡普些微的不同，在于他考虑的议题专注在搜寻型问题。这类问题不仅仅是找到解答存在与否，还必须要输出解答。他提出了六个NP-完全的搜寻型问题，并且还附加证明了一个能在最佳时间内解决这问题的算法。
_START_SECTION_
定义
_START_PARAGRAPH_
对于一个决定性问题，如果我们可以使用非决定型图灵机在多项式时间之内解决它，我们称它在NP内。_NEWLINE_一个布尔可满足性问题的成员（instance）是一个布尔表达式，或者说，一些布尔变数跟布尔逻辑运算符的组合。_NEWLINE_对于一个表达式，如果存在某些给予布尔变数真值的方式使得这个表达式的值为真，我们称它可满足的。
_START_SECTION_
概念
_START_PARAGRAPH_
给定任何NP的决定性问题，建立一个可以在多项式时间内解决此问题的非决定型图灵机。然后，对每个输入，建立一个布尔表示式，告诉我们这个输入进去“是否会正确运作，停止，并且回传答案为真”。那么，这个表示式就是可满足的，当且仅当这个机器正确的跑完这个输入，并且会停止，回答这个输入是正确的。这样，问题“这个我们建立的表示式是否可满足”，与问题“这个图灵机是否会回传"真"”就会变成等价的问题。
_START_SECTION_
结果
_START_PARAGRAPH_
这个定理的证明展现了任何NP问题都可以在多项式时间内归约成（另外事实上，只需要对数空间）转换成一个布尔可满足性问题。这代表如果布尔可满足性问题可以用图灵机在多项式时间内解决，那么所有NP内的问题都可以在多项式时间内解决，因此复杂度类NP就会等于复杂度类P。_NEWLINE_NP-完全的重要性在1972年因为理察·卡普的论文"Reducibility among combinatorial problems"而清楚的表现出来。里面列出了二十一个有关组合和图论的问题（卡普的二十一个NP-完全问题），证明里面的每个均因为其难以解决而恶名昭彰的问题都是NP-完全。