最后一个简化的例子

子集和问题是确定一个正整数集S是否包含一个和为目标值t的子集的问题。这可以表示为一种语言：

subset - sum = { | S包含一个求和为t的子集}

这种语言是NP语言，因为非确定性图灵机可以在多项式时间内猜测子集，计算子集中元素的和，并确认子集和等于t。

为了表明子集- sum在NPC中，我们将3SAT约简为子集- sum。该约简将3cnf公式φ作为输入，并从该公式构造一组整数S和一个目标值t。

下表显示了集合S的结构以及如何构造t。该表由一个3cnf公式φ构造，它有l个变量和k个子句。

	1	2	3	4	⋯	l	c1	c2	⋯	ck
y1	1	0	0	0	⋯	0	1	0	⋯	0
z1	1	0	0	0	⋯	0	0	0	⋯	0
y2	0	1	0	0	⋯	0	0	1	⋯	0
z2	0	1	0	0	⋯	0	1	0	⋯	0
y3	0	0	1	0	⋯	0	1	1	⋯	0
z3	0	0	1	0	⋯	0	0	0	⋯	1
⋮	⋮	⋮	⋮	⋮	⋮	⋮	⋮	⋮	⋮	⋮
yl	0	0	0	0	⋯	1	0	0	⋯	0
zl	0	0	0	0	⋯	1	0	0	⋯	0
g1	0	0	0	0	⋯	0	1	0	⋯	0
h1	0	0	0	0	⋯	0	1	0	⋯	0
g2	0	0	0	0	⋯	0	0	1	⋯	0
h2	0	0	0	0	⋯	0	0	1	⋯	0
⋮	⋮	⋮	⋮	⋮	⋮	⋮	⋮	⋮	⋮	⋮
gk	0	0	0	0	⋯	0	0	0	⋯	1
hk	0	0	0	0	⋯	0	0	0	⋯	1
t	1	1	1	1	⋯	1	3	3	⋯	3

该表包含两行，对应φ中的每个变量xi。标记为yi的行对应以非否定形式出现的xi，而标记为zi的行对应以否定形式出现的xi。对于φ中的每个子句，表中还有一个标记为cj的列。如果变量xi在子句cj中以xi的形式出现，我们在表的第yi行，第cj列中放一个1。如果变量xi在子句cj中以xi的形式出现，我们在表的第zi行第cj列中放一个1。

数字t是精心构造的，用来表达系统中赢博体育相关的约束条件。关于表的列和数字t需要注意的第一件事是，当我们对该列求和时，没有列包含足够多的1来触发进位操作。

接下来要注意的是，其和为1的列表示公式中的每个变量必须为真或假的约束。通过强迫第一列的和等于1，我们本质上是强迫我们自己选择行的一个子集以这样一种方式，即在这个子集和中的前l列中，每列都不包含除了一个1以外的任何东西。

第二组列的和必须全部为3，它们表示每个子句必须至少有一个计算结果为true的项的约束。为了使某一列的和达到3，我们可以从第g行和第h行中为我们的子集选择数字。这些数字将允许一个给定的列和最多等于2，所以我们必须至少再选择一个列中有1的行来得到3的和。在正确的列中选择一个具有1的行，对应于强制我们选择的那一行的变量求值为真。

总结第七章的主要思想

定义语言L在P类中，如果存在一个多项式时间决定器。

定义如果存在一个多项式时间的不确定性图灵机来决定L，则可决定语言L属于NP类。

定义可判定语言L在NP类中，如果该语言是多项式时间可验证的。语言的验证器是图灵机程序V，当给定一对 ，其中w和c都是字符串时，该程序可以使用c在多项式时间内确定w是否在L中。

定义图灵可决语言L是np完全的，如果

1. L∈np
2. 适用于赢博体育其他语言一个 ∈ NP我们有一个 ≤_P l

Cook-Levin定理SAT是np完全的。

如果A和B都在NP中，A是NP完全的，且A≤P B，则B是NP完全的。

其他np完备语言的示例

Sat≤p3sat

3sat≤p团

团≤p顶点覆盖

3sat≤p≠sat

≠sat≤p max-cut

3sat≤3color

3sat≤p子集和

NP中语言的通用决策器

如果A在NP中，则存在A的多项式时间验证者V。验证者在 对上工作，其中w是可能在A中也可能不在A中的输入，c是从某个证书空间c (w)中选择的证书。

这是一个图灵机，它可以在验证者V的帮助下决定a：

输入w：

1. 对于每个c∈c (w)：
1. 在 上运行V。
2. 如果V接受，停止并接受。
2. 停止并拒绝。

这台机器是一个决定器，因为证书空间C(w)是有限的，而V在多项式时间内运行。

这台机器不能在多项式时间内决定A，因为尽管C(w)是有限的，但对于赢博体育np完全语言，C(w)的大小都不是|w|的多项式。

以下是一些np完备语言及其证书空间大小的示例：

语言	典型的c	C的大小(w)
3坐	一个T的列表，F的赋值n变量φ	2n
集团	以下是k团中的顶点	|V|选择k
3颜色	中的顶点的颜色分配列表V	3|V|
子集-总和	的子集中的数年代	2|年代|

计算机科学中最危险的定理

定义A图灵可决语言B是np完全的，如果

1. B∈np
2. 适用于赢博体育其他语言一个 ∈ NP我们有一个 ≤_P B

如果A和B是图灵可决语言，且B在P中，且A≤P B，则A在P中。

定理若B是NP完全且B∈P，则P = NP。

证明就是把定义和前面的定理结合起来。