图同构问题属于 P?

作者: , 共 725 字

更新:证明的关键一步发现错误,作者更新了论文,结论甚至论文标题都改了(废话),新版本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.136
很多人一看到 NP-hard ,就从字面上理解成为比 NP 还难的问题。但如果这里的「更难」指得是解决问题所花费时间更长的话,这个论断是不正确的。从算法角度来看, NP-hard 问题的确比 NP 难,但比 NP 还难(指花费时间更多)的问题却不见得是 NP-hard 的。
本科时有同学扫雷最快可以在 60 多秒完成高级难度,让我这种最快 130 秒的人非常惭愧,当时就想着编一个全自动的扫雷程序,不过一直也没写。今天才知道,原来扫雷问题是NP 完全的...
上篇文章已经提到, P vs NP 是理论计算机科学的核心问题。从数学的角度来说,它和其他历史上有名的数学问题一样,给与人们一个智力上重大的挑战。而更为重要的是,在无数与计算有关的的学术领域中, NP-完全问题以各种不同形式层出不穷。因此,这并不是一个纯粹的与世独立的智力游戏,而是对计算机科学有全面影响力的问题。
Xie Xie 给我看了一个链接性能调优--永远超乎想象,里面提到了素数筛法的复杂度,作者用实验发现此筛法是线形的。
上篇文章扫雷是 NP 完全问题之后,You Xu提到"不光扫雷是 NP 完全问题,空当接龙问题也极有可能是一个 NP 完全问题。目前最好的通用 planner 只能解半副牌"。他说对了,不光扫雷, Windows 自带的游戏都是 NP 完全的。Windows 自带的游戏除了扫雷,还有空当接龙和蜘蛛纸牌。
Game Theory 即博弈论,目前在经济学中运用得最多(纳什更因为他在这上面的工作拿到了诺贝尔经济学奖)。但在最近几年,理论计算机界对它的研究也很热。
前面已经提到了显示中大多数难解问题问题最后都被证明是 NP-完全问题。这意味着,除非 NP=P ,它们是不可能有多项式时间算法的(而且,在这篇文章提到即使 NP=P ,人们也可能找不到一个 NP 完全问题的「有效」算法)。
在 slashdot 上看到一篇科技新闻,两个数学家(其中一个来自于 MIT )和一个计算机学家,在 arXiv 上发表了一篇论文《HOW TO GAMBLE IF YOU』RE IN A HURRY》(PDF 版链接),是最近几天很热门的一条新闻。
IT » MathJax, latex, wordpress
此插件已经不再维护,但理论上可继续使用。
Rob Pike, 最伟大的 C 语言大师之一 , 在Notes on C Programming(英文原文)中从另一个稍微不同的角度表述了 Unix 的哲学: