最近很热的一条新闻，关键词：复旦大学，大三本科生，世界级猜想，内地数学家已经阔别了整整十八年的最高级别的会议…

论文信息：

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位居第二作者，目前第一作者为香港大学计算机系教授。但此论文作者顺序应该是按照SoCG的惯例为字母排序，所以实际第一作者未知。

Minimum Manhattan Network问题是指平面上有若干个点，只使用水平和垂直的线段把它们都连起来，求需要的最小线段总长度。论文的结论是从3SAT规约证明了此问题是NP完全的。NP完全问题已经成千上万个了，大部分的NP完全问题证出来都没人看。此结果比较重要是因为Minimum Manhattan Network本身的应用比较广泛。但要说它是世界级难题也太那个啥了。

此新闻出现在高考填报志愿前期，对复旦大学招生应该助益不少，同样28岁清华研究生任湖北宜城市长这条新闻也是如此