当前位置： 查字典图书网> 算法> 自动机理论、语言和计算导论(英文版.第3版)> 书中有一个错误

书中有一个错误

张觉非 对 自动机理论、语言和计算导论(英文版.第3版) 的书评 发表时间：2012-12-28 23:12:32

书中通过将 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）写了信。他说这问题早就发现了。

有用 2 无用 0

您对该书评有什么想说的？

对“书中有一个错误”的回应

CJ
CJ 2013-12-16 23:46:44

版次往往有N次印刷, 会在后续刷次勘误, 我在另一本Sedgewick的Algorithms, 4E有过经验
不过既然勘误表没有, 那后续印次纠正的可能不大

回应他
张觉非
张觉非 2013-12-16 13:08:02

没有说。这影印版是第三版，好像没有更新的版本。网上勘误表里也没有，我写信前查过。

回应他
CJ
CJ 2013-12-16 00:50:47

他是说已经出过勘误表了, 还是在后续印次里纠正了?

回应他

《自动机理论、语言和计算导论(英文版.第3版)》热门书评

自动机理论、语言和计算导论(英文版.第3版)

书名： 自动机理论、语言和计算导论(英文版.第3版)
作者：
出版社： 机械工业
原作名： Introduction to Automata Theory, Languages, and Computation (3rd Edition)
出版年： 2007-9
页数： 535
定价： 59.00元
ISBN： 9787111223924