正当志愿填报时-复旦大三本科生解决世界级几何猜想?

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

 

论文信息:

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岁清华研究生任湖北宜城市长这条新闻也是如此 :D

查看更多关于, , 的内容。

你可能感兴趣的
相关文章

11条留言 -> 跳到留言表格

  • At 2009.06.23 04:56, YauzZ said:

    这(NP=P?)啥时候是个头哦.

    • At 2009.06.23 11:29, wealk said:

      哈哈 有意思

      • At 2009.06.23 12:53, foo said:

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

        ——这个分析比较靠谱

        • At 2009.06.25 23:48, dsfdsf said:

          test

        • At 2009.06.24 22:02, THINK said:

          http://www.tcs.fudan.edu.cn/~sun/mmnc.rar
          演示demo
          http://www.tcs.fudan.edu.cn/~sun/SCG.pdf
          文章

          这是孙贺的主页上所给的东东

          • At 2009.06.28 13:13, Jacse said:

            说到底就是炒作咯。

            • At 2009.06.28 16:02, AI said:

              呵呵,报纸吗都是尽量吹

              看了一眼,想法还是比较巧妙的,本科生不易了

              • At 2009.06.29 21:51, sog said:

                拜托师弟,

                先帮我恢复一下原 http://sog.zhiqiang.org 的内容。

                文章数据应当都还在,通过 sql控制台 update 权限 字段 private 为 published

                时间紧急,拜托,回京详谈。

                • At 2009.06.29 21:52, sog said:

                  历经十年时间得证一个公式,希望有机会与你参详!

                  二加二在三点钟等于四,(维特根斯坦 语)

                  二加三在四点钟等于五,(以下为自己求证心得)

                  二加三在四点钟不等于五,

                  二十三在四点钟不等于五。

                  • At 2009.06.29 22:12, sog said:

                    嘴┆真┆ ┆。┆-┆-┆ ┆-┆我┆ ┆发┆不┆中┆这┆ ┆f┆
                    巴┆是┆ ┆ ┆-┆-┆他┆-┆操┆ ┆表┆能┆译┆篇┆ ┆u┆
                    自┆鸡┆ ┆ ┆-┆-┆-┆-┆ ┆ ┆。┆在┆文┆文┆ ┆c┆
                    由┆巴┆ ┆ ┆-┆-┆-┆-┆-┆ ┆ ┆百┆竟┆章┆ ┆k┆
                    。┆比┆ ┆ ┆妈┆-┆-┆﹀┆-┆ ┆ ┆度┆然┆的┆ ┆,┆

                    • At 2009.07.01 22:00, ddd said:

                      RFTGZRTZTZU

                      (Required)
                      (Required, not published)

                        B | I | U | D | 添加链接 | 插入引用 | 插入代码 | 插入表情 | | + | ?
                      guest | 注册 | BBS | 管理 | English | 繁體 | https
                      Loading...
                      Loading...
                      Loading...