现在恢复了十年的计算机科学突破！

这几乎是前所未有的。首先，我们在计算机科学领域取得了重大成就。几个月后，它突然收回，在整个社区引起了一阵失望。但是，令我们感到欣慰的是，仅过了几天，它就恢复了。

数学越来越草率了吗？证明在发布之前受到的关注太少了吗？不，只是平均证明越来越复杂。我们可能正在进入一个时代，在我们相信之前，证据必须像优质葡萄酒一样沉淀并成熟。

是的，当涉及诸如数学之类的纯粹逻辑学科时，使用“相信”一词是很奇怪的，但是现代数学证明是建立在许多其他结果之上的，因此需要从上到下验证纸牌屋。您是否已涵盖所有可能性，这也是一个长期存在的问题。这是不成文的，但是众所周知，任何数学证明都必须处理某件事可能发生或不可能发生的所有方式，如果您只是错过了一种全新的做事方式呢？

在声称2016年取得突破之后，拉斯洛巴拜（LaszlóBabai）在2017年1月4日发布撤稿。现在我们有一个帖子声称该证据已修复：

2017年1月9日更新：恢复了拟多项式声明

1月4日，我宣布Harald Helfgott在我的Graph同构测试分析中指出了一个错误。该错误使我先前关于拟多项式效率的主张无效。公告文本附于下文。

1月7日，我发现了引起问题的“ Split-or-Johnson”例程中的递归调用的替代项。通过这种修改，我声称图同构测试在准多项式时间内运行（现在确实如此）。

替换由几行伪代码组成，这些伪代码通过有关一致性配置结构的简单新引理进行分析。

我正在处理更新的arXiv发布。

引人注目的-谁会想到数学中有这种戏剧性？好吧，任何与数学有任何联系的人！

更新和原始新闻如下：

---

图同构更新2017年1月4日

听起来可能太过戏剧化了，当您发现它是什么时，您可能想使用术语“深奥”，但是针对图同构问题的拟多项式时间算法的发现很有趣而且很重要，并且在2016年是个头条新闻。现在我们有一个障碍。它的创始人LászlóBabai于2017年1月4日发布撤回声明。

这对2017年来说并不是一个好的开始，但值得赞扬的是拉兹洛巴拜（LaszlóBabai）如此开放。结果很重要，请参阅下面所附的原始新闻报道，因此已经仔细检查了。不幸的是，尽管本文的大部分内容都没有错，但时序分析中存在一个缺陷，该缺陷将结果从准多项式时间变为次指数时间。

“论文的技术内容实际上保持不变。先前的分析针对组合式 Split-or-Johnson”过程的一个递归步骤进行了分解；但是“ Split-or-Johnson”定理在更新的时序分析中仍然有效。所有其他结果均不受影响。我正在处理更新的arXiv帖子（具有不同的标题），该帖子还将根据一些同事的评论来改进演示文稿。

我要感谢哥廷根大学和CNRS的Harald Helfgott发现了这个错误，并花费了几个月的时间对本文进行了详尽的研究。Helfgott将在Bourbaki研讨会系列中发表他对算法的阐述（带有修改后的分析）。

结果仍然令人印象深刻，但并没有十年的突破-无论如何这可能是一个头条新闻。

也有希望可以修正该证明的范围：

“感谢哈拉尔德”的努力以及他对似乎最细微的细节的不懈关注，我现在相信经过修改后的分析得出的结果是正确的。此外，本文介绍的新技术为进一步取得进展提供了框架和工具。

这也是现代数学如此复杂的一个很好的例子，证明直到长期存在才成为证明。我们喜欢认为证明是从前提到定理的一系列可证明的推论，但是今天很明显，“可证明的”含义与欧几里得时代的含义有所不同。也许我们的确需要计算机帮助来证明。

接下来是我在2016年10月写的新闻条目，需要对新发现的兴奋感激地加以阅读：

LászlóBabaihas在2015年11月10日星期二于芝加哥发布了演讲摘要：

我们概述了一种解决图同构（GI）问题以及字符串同构（SI）和CosetIntersection（CI）拟多项式（exp（polylogn）time）问题的算法。

如果他确实提出了这样的算法，它将负责计算机科学的整个领域，因此需要一些背景来解释这种说法。

首先，我们必须找出什么是同形问题，而且听起来并不那么困难。

图是节点和连接节点的弧的集合-想一想路网。

图同构问题只是确定两个图是否相同。这听起来很简单，但是您必须找到与哪个节点相对应的节点。例如，这两个图看起来不同，但实际上它们是相同的：

信用：维基百科

颜色为您提供了两者之间的映射，揭示了它们是相同还是同构-相同的形状。

这是一个决策问题-两个图是同构的-看起来很困难。可以通过解决问题所需的时间随问题规模的增加而增加的方式来衡量问题的难度。

例如，如果图形同构问题的时间增加了nc

其中n是图中的节点数，c是某个常数，则为多项式难度。

乍一看，图同构似乎是一个更加困难的问题，并且可能花费的时间在节点数上呈指数级-例如cn

请注意，cn变得比您要考虑的任何多项式都要大，例如随着n越来越大，c2 c3 c4等等。

好的，因此很难找到图同构问题的解决方案，但是如果我给您提供解决方案，即我声称是同构的节点映射列表，则可以非常快速地检查我的解决方案。

可以快速检查提出的解决方案的属性问题，即检查算法以多项式时间运行，属于NP非确定性多项式时间。

所有容易解决的问题，即可以在多项式时间内解决的问题，因此都在P中，也都在NP中，因为您显然也可以检查多项式时间中的解决方案。

P和NP这两个复杂性类是计算机科学的核心。我们真正要回答的一个问题是P和NP不同或相同。NP中的某些问题似乎要困难得多-这些是NP的完整问题。可以证明，如果一个NP完全问题具有多项式解，那么每个NP完全问题也都具有多项式解，因此P = NP。

如果P = NP，那么坏事就可能会发生，因为许多加密依赖于难以解决的NP完整问题，如果它们在P中，则还不够困难。

现在我们回到图同构问题。这是NP中尚未被证明存在于P或NP中的少数几个众所周知的问题之一，在获得最新结果之后，我们仍然不能确定，但​​并不重要。

我们需要回答的下一个问题是什么是准多项式时间。编写多项式时间的另一种方法是：

nc = ec（登录）

您可以看到它是正确的，因为logen是您必须乘以e以获得n的原因。

拟多项式时间为：

ec（登录）^ k

对于某些k，它减少了k = 1的多项式时间。如果k大于1，则时间的增长速度快于任何多项式时间算法，但远小于指数时间算法。

因此，假设已验证了Babai的证明，我们得到的结果是，尚未被证明是NP完全的NP问题具有拟多项式时间算法。关键是，它与多项式时间非常接近，因此差别不大。

那么，这对于NP = P意味着什么？

这就意味着一个NP问题的例子，乍一看似乎并不难。过去有其他例子-证明EXP中的数字是素数还是不是素数，但是最近发现了一种算法在P中。

难道EXP中出现的其他NP问题是拟多项式吗？难道是像分解这样的NP完全问题可能是拟多项式吗？

您可能会争辩说，如果NP完全问题是拟多项式，那么NP仍然不是P，但是就加密之类的实用性而言，它们实际上是相等的。您可以说不需要证明NP = P即可证明NP = QP就足够了。

令人惊讶的是，惊人的理论工具似乎对证明这种结果至关重要。建议是证明依赖于简单组的分类。找到有效的算法真的需要这种高级方法吗？

大概。