[-]

芝加哥大学数学系著名教授László Babai宣布发明了一种全新的算法，该算法可显著地简化计算机科学领域某些众所周知的困难问题。 这一突破性的进展使得很多算法领域的专家们开始怀疑一直以来他们信以为真的理论也许并不靠谱。同时，该发现也提醒我们，或许可以取得类似突破，使得攻破数据加密算法变得更加容易

László Babai教授将于该校举办三场系列讲座，详细解释他所发明的新算法如何解决著名的图的同构问题(Graph Isomorphism problem)。本周二和周四(11月10日/12日)的两场讲座均人满为患。图的同构问题是指由计算机判断给定的两个图——每个图由一些“点”(vertex)和“边”(edge) 构成——是否具有完全相同的结构。

Babai 教授的讲座非常令人鼓舞。过去三十余年来，图的同构问题都被认为很可能是最难以使用计算机解决的问题之一。若Babi教授的算法正确无误，则这一看似颇具挑战性的问题事实上更可能属于一类易于解决的算法问题，也即存在复杂度至多为多项式时间(complexity class P)算法的问题。

“这一突破使得大家浮想联翩，”佐治亚理工学院(Georgia Institute of Technology)从事计算理论研究的Richard Lipton教授表示，“他把这个问题的难度降低了数个级别”. 麻省理工(MIT)的副教授Scott Aaronson在了解Babai教授的发现后，在他的博客上表示这可能是“计算理论领域近十年来最重要的突破”

在计算机领域，要衡量一个问题的困难程度，科学家们通常考虑随着问题规模的上升，所需要多少的计算能力的增加速度。根据这一标准，图的同构问题被归类为极其困难的问题，因为随着输入图的尺度增加，解决该问题所需要的计算能力几乎呈指数型增长。

该算法由Babai教授和俄勒冈大学(University of Oregon)的Eugene Luks于1983年初次发表。Babai教授称，当输入的图的尺度增加时，他的新算法需要的额外计算能力并不会急速增加。该算法的存在使得图同构的问题的困难程度被显著降低。

Babai教授表示在其研究成果经过同行评审并正式发表之前，不愿接受采访。但他对一名参加他讲座的激动听众说，其论文的预览版将会“很快”发表。

Lipton教授则表示，在完整的论文面世之前，我们应当谨慎对待任何声称的突破性成果。但是凭借Babai教授在业内的崇高声望，大家纷纷表示他所取得的成果很有可能是真实可靠的。“他老人家可是业内的泰山北斗”，Lipton教授说。

若Babai教授的成果最终被确认有效，这一发现目前也只会在计算理论的专家圈子内掀起一些波澜。图的同构问题在某些领域内具有一定的应用价值。例如在数据库内检索特定的分子结构，因为分子结构可以简单地通过图来表示。 不过该问题已经存在类似的替代解决方案。

Babai教授还宣称，在因式分解问题上也取得了类似的突破。因式分解被认为和图的同构问题具有相同的困难程度，但该问题的潜在影响力比图的同构问题更加深远。 因式分解也即将一个数分解为其所有质因子。这一问题是最为常用的加密技术的基石，而该加密技术则被广泛的用于数据和因特网上的通讯加密。

即便使用当前已知的最佳算法，因式分解问题仍然和图的同构问题一样具有很高难度。同时由于因式分解具有某些图的同构问题所不具备的数学性质，Babai教授的算法目前无法用来解决因式分解问题。不过，Lipton教授认为，这一发现的意义在于提醒人们某些长期以来被奉为真理的理论或许会被某些新的算法推下神坛。

“如果能够找到解决因式分解的快速算法，即使只是理论上有效，这也足够让密码学专家们如坐针毡了”， Lipton教授说。当前的加密技术能够被暴力破解，但是如果加密算法使用的秘钥足够长，暴力破解需要使用海量的计算资源。若这方面的算法有所突破，政府机构等或能够切实地利用现有的超级计算机来对当前使用的加密算法进行暴力解密。

即便理论上有效的快速因式分解算法尚不能投入实践，这也足够督促科学家们进行进一步的探索和尝试去破解这一问题，Lipton教授补充道，“密码学专家们恐怕不能再信誓旦旦的公开表示‘我的加密算法是安全的，因为该算法用到了因式分解’。”

本文译自 MIT Technology Review，由 Grey Yang 编辑发布。

PREV : 吃猫粮的诺奖经济学家
NEXT : 俄罗斯忠犬的290公里回家路