你好，请 登录 或 注册 · 九点指南

图同构问题属于P？

　　更新：证明的关键一步发现错误，作者更新了论文，结论甚至论文标题都改了（废话），新版本On the graph isomorphism problem。
　　提交论文到arxiv不需要审阅，一般人都可以提交，所以常有些错误的论文甚至民科作品（在物理和数学领域更多一点）。号称解决图同构问题甚至p vs np以前也有过，不过这次文章的作者的publication记录不错，有2篇ann. of Math.，数量也不少，所以大家稍微关注一些。
　　事实上，这么大的结果发表之前应该找人审查的，这次出问题估计在于作者是个数学家，和理论计算机界接触较少的缘故。
　　更新于2008.1.5
　　在P vs NP - 问题概述我提到了两个自然的问题，一个是大数分解（给出一个数的质因数分解式），另一个是图同构问题（给出两个图，它们是否同构），它们既没有被证明是P的，也没有被证明是NP-完全。但昨天来自芝加哥Illinois大学的Shmuel Friedland给出了图同构问题的P算法，论文Graph isomorphism is polynomial（正确性未知，但看作者的p......    (查看原文)