新算法破解图同构问题

jopen 8年前

芝加哥大学的数学和计算机科学教授László Babai 在 11 月 10 日宣布了能有效解决图同构问题的新算法。斯坦福大学的计算机科学家 Ryan Williams 说,他一开始以为是个玩笑,特地查了下那天是不是愚人节。他认为新的算法有可能是过去十多年计算机科学理论最重要的突破。

Babai 的算法还需要被仔细检查,他思考这个问题已有 30 多年了。他声称算法能在拟多项式时间内判定最复杂的图,他拒绝接受采访,表示需要先确保能经受同事们的多轮拷问。麻省大学的理论计算机科学家 Neil Immerman 说,一位数学家在宣布重大发现前没有递交书面证据是不同寻常的做法,但 Babai 是非常聪明和可靠的人,是图同构问题的顶级专家,相信他能证明他的声明。

来自: Solidot