书中有一个错误

书中通过将 3SAT 问题多项式时间规约到独立集问题。证明了独立集问题是NP完全的。


但他的独立集问题IS，是这么表述的：

给定一个无向图(n个顶点)和一个数k，问这个图存不存在k个顶点的独立集。

这个问题是P的。因为，对于题面中给定的k，从全部n个定点中选出k个顶点的子集的个数是 c = C(n,k) = n! / (k!*(n-k)!)。这个数是n的多项式。挨个考察这 c 个顶点子集是否独立，每次考察需要多项式时间。一共有多项式次考察，每次考察又是多项式时间，于是这个算法总时间是多项式的。

也就是说，IS问题，像书中那么表述的话，是P不是NP，自然也不是NP-Complete。

其实书中没有将3SAT问题归约成像上面陈述的那种IS问题。问题就在于上面陈述中的k，是一个与n无关的量。

书中用3SAT问题中的那个 3CNF构造出来那个图，然后找它的独立集，要求要找的独立集的定点数不是一个与n无关的k，而是k=n/3。3CNF的每个文字一个顶点，每个字句三个顶点，出来的那个图，要想判断原来那个3CNF是否可满足，就要看存不存在k=n/3个顶点的独立集。

如果k是n/3，那么按上面说的那个算法，需要遍历考察的子集数就是 C(n,n/3)了，这就不是多项式，而是指数了。

给作者（Ullman）写了信。他说这问题早就发现了。