新算法破解图同构问题

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

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