更新：证明的关键一步发现错误，作者更新了论文，结论甚至论文标题都改了（废话），新版本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（~~正确性未知，但看作者的 publish list 是有保证的~~）。
在 70 年代NP-hard概念出来后不久，绝大部分「自然」的难题最后都被证明为 NP-hard ，除了三个，他们分别是：
- 线形规划：后有多项式的内点法。这里要提一下的是，被广泛应用且效果极佳的单纯型法并没有证明是多项式算法。
- 图同构：~~刚被证明属于 P~~。
- 素数判定&大数分解：前者已找到多项式算法，后者找到多项式量子算法。
~~看来现在还能做的只有大数分解的多项式算法了~~。大家加油啊...
Q. E. D.
