NP类，NP完全性以及Levin-Cook定理
本论文将会给出的定理让我们推测（而不是推导）这些问题，包括类似于它们的问题，将会是永恒的难解的。——Richard Karp，1972
不幸的是，我们距离理解“2”的神秘力量仍然还有许多年……2-SAT问题是容易解决的，但是3-SAT问题却非常困难；二维的匹配非常简单，但是三维的匹配却异常困难。为什么会这样？天哪，为什么会这样？——Eugene Lawler
到此为止，我们已经证明了3SAT问题并不会比二次方程、独立集、最大割和最长路问题更难。但是证明这些问题在计算上等价，我们需要从其它方向给出证明。最终结果是：我们可以将所有的问题一举归约为3SAT问题。
事实上，上述的结果远远超出了那些特定问题描述的范畴。我们在上一章讨论的所有问题，以及很大一类其它问题，都具有一个共同特点：它们都是搜索类问题，且目标都是——给定一个实例，判定是否存在一个解使得某个条件成立，而这个条件可以在多项式时间内被验证。例如，在3SAT问题中，布尔公式就是一个实例，而它的一个解是对于变量的一个赋值；在最大割问题中，图是一个实例，而它的解则是切割的方法；诸如此类。我们最终发现，所有的类似的搜索问题都能够被归约为3SAT问题。
本章速读：一个非数学的概览
本章，我们将会了解复杂度类的定义——这是本书中最重要的定义之一；还有Cook-Levin定理——这也是本书中最重要的定理之一。直觉上，复杂度类对应的是容易验证结果的一类问题（例如，验证可以在多项式时间内完成）。举个例子，找到一个满足2SAT公式或者3SAT公式的赋值就是类似的问题，因为我们拥有一个对于公式的赋值，而我们可以高效地验证这个赋值是否满足所有的约束。更准确地说，是一个“判定”问题的复杂度类（例如，布尔函数或者语言），这一类问题常常对应确定一个解是否存在，尽管我们将会在16章看到，判定问题和搜索问题实际上是紧密相关的。
正如我们在2SAT和3SAR问题的例子中展示的那样，有一些类中的计算问题（例如，函数）拥有多项式算法，但是有一些则还未发现是否有类似的算法。这是一个极其著名的开放问题：所有的函数是否都具有多项式算法？或者说（用一点数学语言）， 是否成立？本章，我们将会了解到某些感觉上“最难”的中的函数。所谓“最难”，就是说只要其中一个函数具有多项式时间算法，那么所有的中的函数都具有多项式时间算法。这样的函数，我们称它们为完全的。Cook-Levin定理表明，3SAT问题是完全的。我们从这个定理可以构建一个复杂的多项式归约网络，目前，研究人员已经通过此定理证明了数千数学领域、自然科学、社会科学和工程学领域计算问题的完全性。这些结果为我们提供了以上问题无法在最坏情况下被多项式时间算法解决的证据。
图15.1
上图是本章内容的概览。我们用来定义包含所有能够被高效验证的判定问题。本章的主要结果自然就是Cook-Levin定理（定理15.6），该定理表明3SAT问题拥有多项式算法当且仅当类具有多项式时间算法。另一种说法就是说3SAT是完全的。我们将会通过定义两个中间问题NANDSAT和3NAND并证明NANDSAT是完全的，从而进一步证明。
15.1 类
我们下面使用数学定义使得我们之前的描述更加精确。我们将类定义为所有对应上述搜索问题的布尔函数。这就是说，一个布尔函数在中当且仅当对于一个输入串，有当且仅当存在一个串作为解，且使得对于串对满足某些多项式时间的检查条件。形式上，类定义如下：
我们称在中，若存在某个正整数和对于每一个都有一个使得。
图15.2
类对应的是那些解可以被高效验证的问题。这就是说，该类中的函数，当的时候，存在一个长度为关于的多项式的解可以被多项式时间算法验证。
换句话说，对于任何在的，必然有一个多项式可计算验证函数使得对于，必然存在（长度为关于x的多项式）使得。由于的存在证明了，通常被称为证书，见证或者证明。