图同构问题属于 P?

作者: , 共 759 字

更新:证明的关键一步发现错误,作者更新了论文,结论甚至论文标题都改了(废话),新版本 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.

类似文章:
相似度: 0.134
很多人一看到 NP-hard ,就从字面上理解成为比 NP 还难的问题。但如果这里的「更难」指得是解决问题所花费时间更长的话,这个论断是不正确的。从算法角度来看, NP-hard 问题的确比 NP 难,但比 NP 还难(指花费时间更多)的问题却不见得是 NP-hard 的。
本科时有同学扫雷最快可以在 60 多秒完成高级难度,让我这种最快 130 秒的人非常惭愧,当时就想着编一个全自动的扫雷程序,不过一直也没写。今天才知道,原来扫雷问题是 NP 完全的 ...
上篇文章 已经提到, P vs NP 是理论计算机科学的核心问题。从数学的角度来说,它和其他历史上有名的数学问题一样,给与人们一个智力上重大的挑战。而更为重要的是,在无数与计算有关的的学术领域中, NP- 完全问题以各种不同形式层出不穷。因此,这并不是一个纯粹的与世独立的智力游戏,而是对计算机科学有全面影响力的问题。
IT » MathJax, latex, wordpress
此插件已经不再维护,但理论上可继续使用。
Rob Pike, 最伟大的 C 语言大师之一 , 在 Notes on C Programming ( 英文原文 ) 中从另一个稍微不同的角度表述了 Unix 的哲学 :