Princeton的Sanjeev Arora和Boaz Barak最近写了一本计算复杂性方面的书：Complexity Theory: A Modern Approach，其初稿提供下载，并承诺出版后也会继续保留——要是所有作者都这么好心就好了。
下面这段摘自于第二章NP and NP completeness，写得很有趣。为什么多数人不同意P=NP呢？因为
“if (3SAT has a O(n^2) algorithm), then this would have consequences of the greatest magnitude. That is to say, it would cl...

上篇文章已经提到，P vs NP是理论计算机科学的核心问题。从数学的角度来说，它和其他历史上有名的数学问题一样，给与人们一个智力上重大的挑战。而更为重要的是，在无数与计算有关的的学术领域中，NP-完全问题以各种不同形式层出不穷。因此，这并不是一个纯粹的与世独立的智力游戏，而是对计算机科学有全面影响力的问题。
历史上的进展
从上个世界70年...

P = NP?
这个问题，作为理论计算机科学的核心问题，其声名早已经超越了这个领域。它是Clay研究所的七个百万美元大奖问题之一，在2006国际数学家大会上，它是某个1小时讲座的主题。
要说起P和NP是什么东西，得先从算法的多项式时间复杂度谈起，注意，这里面的两个P都是指Polynomial。
一个问题的规模指的是输入的总位数，比如一个n个数的排序问题，输入规模...