最近很热的一条新闻，关键词：复旦大学，大三本科生，世界级猜想，内地数学家已经阔别了整整十八年的最高级别的会议…
 
论文信息：
Minimum Manhattan Network is NP-Complete（PDF版本） Francis Y. L. Chin, Zeyu Guo and He Sun
被25th Annual Symposium on Computational Geometry(SoCG)接收，SoCG是计算几何领域顶级会议。
关于作者排序：复旦大三本科生Zeyu Guo位居第二作者，...

好久没有写我的理论计算机初步系列了，其实复杂性这一块，虽然平时经常遇到，但由于问题都过于本质和困难，想这方面问题的时间反而不多。Ko教授就跟我说也许NP verse P这个题并不难，只不过大家认为它很难，结果就没有多少人去做了，大家一遇到这个问题都远远得绕开。话虽如此，我还是不敢去碰的。
很多人一看到NP-hard，就从字面上理解成为比NP还难的问题。但...

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