数学家声称复杂性理论有所突破

几天来,关于所谓的复杂性理论中多年来最大进步的谣言一直在点亮互联网。 这是恰当的,因为这一突破涉及比较网络,就像研究人员的在线连接网络一样。 LászlóBabai是伊利诺伊州芝加哥大学的数学家和计算机科学家,他开发了一种数学配方或“算法”,据称可以采用两个网络 - 无论多大和纠结 - 并告诉它们实际上是否相同,比以前的最佳算法少得多的步骤。 计算机科学家们非常热衷于此,因为这项任务对于难以解决的问题来说是个典型的问题。

“如果这是正确的,它可能是十年来理论上的计算机科学成果,”剑桥麻省理工学院的计算机科学家和博主Scott Aaronson说。

复杂性理论基本上是研究计算机难以解决的问题。 在其中,关键是如何解决问题所需的步骤数随着输入的大小而增加。 例如,假设您要确定给定数字983或105227是否为素数且不能用其他数字除。 该计算中的计算步骤数随着数字中的位数而增长相对缓慢。 通常,它随着数字n的增长而增长,增加到固定功率 - 类似于n 2 像这样的表达式称为多项式,因此该问题可以在“多项式时间”中解决,并且在复杂性类“P”中。

另一方面,假设您想将给定数字(例如21,112,331)划分为所有因子。 到目前为止,还没有人找到多项式时间算法来做到这一点。 因此,分解被认为更难并且存在于更广泛的问题类别中,称为“非确定性多项式”的NP。 粗略地说,对于更难的NP问题,步数被认为随着输入增长中的位数呈指数增长,如2 n ,其变得比n 2快得多。 (例如,100 2仅为10,000; 2到100的功率超过100万亿亿。)

现在,Babai已经证明了一个被认为是在较硬的NP端的问题更接近于更容易的P端。 任何网络 - 无论它代表传播流感的人还是生物体内相互作用的蛋白质 - 都可以被描述为一组点或节点,通过直线或边缘连接,象征着节点之间的相互作用。 因为节点可以以任何旧方式向下移动,所以具有相同连接排列的两个图形可能看起来不同(见图),尤其是当图形变得更大且更复杂时。 在“图同构问题”中,挑战在于确定两个图是否真的相同。 正如他今天宣布的那样,巴拜已经找到了解决这个问题的新算法。

对于以前最好的方法,由Eugene Luks(Eugene的俄勒冈大学的数学家和计算机科学家)于1983年发明,步骤数随着要比较的网络中的节点数量几乎呈指数增长。 在Babai算法中,步数仅比多项式时间略快。 这听起来像是比较灰色阴影,但对于专家而言,质量差异令人兴奋。 “假设这个结果成立,它将成为[理论计算机科学]的宝石,并且是一个令人难以置信的实时见证,”一位读者在Babai的谈话之前写了一篇关于Aaronson博客的文章。 “超级刺激!” 在另一个博客上写了一个读者。

具有讽刺意味的是,即使网络和图形无处不在,现在看来,新算法也不太可能具有广泛的实际应用,Aaronson说。 这是因为当前的算法已经可以快速解决绝大多数图形的图形同构问题。 Aaronson解释说,如果它坚持下去,新算法只能证明阻碍当前算法的棘手情况也能有效地解决。 新算法也没有涉及复杂性理论中的最大问题:NP类是否真的与P类不同。研究人员通常认为这是真的,如果他们错了,许多事情 - 例如互联网密码技术 - 将是非常脆弱的。 但是没有证据证明NP不等于P.

Aaronson说,新工作的真正进步是将关键问题从硬类转移到简单类。 他说,图同构问题一直是个奇怪的问题:人们认为很难知道某些技术属性通常与更容易出问题有关。 现在,可能只是问题并不是那么难。

当然,其他研究人员仍然需要检查巴拜的工作。 他将在大学进行两次演讲,一次是今天一次,另一次是11月24日。 “你仍然需要看到细节,”Aaronson说。 “巴拜的身材仍有可能犯错误。”