图同构问题属于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（正确性未知，但看作者的publish list是有保证的）。
在70年代NP-hard概念出来后不久，绝大部分"自然"的难题最后都被证明为NP-hard，除了三个，他们分别是：
- 线形规划：后有多项式的内点法。这里要提一下的是，被广泛应用且效果极佳的单纯型法并没有证明是多项式算法。
- 图同构：
刚被证明属于P。 - 素数判定&大数分解：前者已找到多项式算法，后者找到多项式量子算法。
看来现在还能做的只有大数分解的多项式算法了。大家加油啊...
很惊人的消息.....你相信我们有生之年能看到P vs NP这个问题的答案不?
我相信能。科技在加速，未来100年相当于过去的500年不止。
文章更新了，那个证明是错的哈
我周五和李老师吃饭的时候李老师就和我说了那个paper已经withdraw了,不过没准可以弄个invited speaker
记着在哪儿看到过：图同构可多项式解答，是由密码学家做出来的。我记错了吗？
你记错了...
非常多的特殊情形比如bound degree graph, planar graph等已经有多项式算法，而且有对一般图的算法在实际运用时也比较快（同线形规划的单纯形法），但对一般的图而言，还没有一个算法被证明是多项式的。
论文错了阿,大家还有机会呢,哈
多项式量子算法...
希望在有生之年能用上量子计算机哈...