1
图同构问题属于 P？
source link: https://zhiqiang.org/cs/graph-isomorphism-is-polynomial.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
图同构问题属于 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~~。
- 素数判定&大数分解：前者已找到多项式算法，后者找到多项式量子算法。
~~看来现在还能做的只有大数分解的多项式算法了~~。大家加油啊...
Q. E. D.
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK