图同构在P/NP问题上重大突破，计算机理论10年最重要成果

芝加哥科学家 László Babai 发明了一种方法，能够用多项式的时间判断两个网络是否相同。

麻省理工学院的计算机科学家 Scott Aaronson 把它称为计算机理论领域十年以来最重要的成果。

斯坦福大学的计算机科学家 Ryan Williams 说，他一开始以为是个玩笑，特地查了下那天是不是愚人节。他认为新的算法有可能是过去十多年计算机科学理论最重要的突破。

图同构在 P/NP 问题的突破，能解决很多计算机的实际问题，毕竟很多任务都都可以归结为网络是否相同上。

图同构中即使很小的进步都会掀起领域波澜。在80年后期的一个理论分会上，一个演讲者在提到有关于图同构是NP问题的证明（他并没有）时，造成了重大的轰动。Babai的宣称更是引起巨大反响。

下文是新智元翻译 Lance Fortnow 教授的文章。他是佐治亚理工计算机科学学院的主席，和László Babai也有过很多合作。我们从他的角度来看László Babai的研究成果和意义。

作者介绍：

Lance Fortnow：计算机科学家，在计算复杂度及其在经济理论上的应用、交互式证明系统上有重要贡献。1989年获得MIT的应用数学博士学位，导师是Michael Sipser。毕业后，于1989—1999年和2003—2007年在芝加哥大学供职，并在2007年获得ACM院士奖。2012年至今，在佐治亚理工学院供职并担任计算机科学学院的主席。

【Lance Fortnow】我在芝加哥待了 14 年，很了解 László Babai，也一起合作解决了我工作中的知名难题。我能想象周二在那个房间，当Babai进行在理论计算机科学史上最令人期待的讲座时，听众们的期待与兴奋。

这篇博文主要解释图同构问题和它在复杂理论研究中的重要性。

假设有两个高中学校，比如诺斯高中和索斯高中，每个高中有1000名学生。现在有一张图（图1），里面每个点表示诺斯学校的一个学生，学生与学生之间Facebook好友关系用一条线来表示。索斯学校也有这样的一张图（图2）。那么能否找到一种图2到图1的点和点之间一一对应的关系，使得图2 和图1 是相同的？这就是图同构问题。

新智元注：例如说这两张图片就等同。

为了判断两幅图是同构的，你可以寻找所有可能的两校学生之间对应方式，但那代表了1000的阶乘（1000！）或者多于4*10^2567种的对应关系。也有减少对应关系数目的方法，比如我们对它加一些限制条件，但是那也是在n（代表学生的数量）的指数级数量的对应关系。

理想状态下，我们希望用一个计算时间为n的多项式的算法来解决这个问题，并且Babai的研究很接近这个结果，找到了一个耗时为n*(log k)^n（对于固定的k）的算法。

把图同构的计算量从n的阶乘、或者n的指数级变成了n的多项式，这在外行看来相差不大。但对于计算机专家来说，这种质的差别能让计算机处理更加复杂的事情。毕竟像社交网络、基因图谱这些巨型网络，要是以传统的方法进行比较和分析，基本上是不可能的事。但如果能把它们归入多项式的时间框架内，就容易处理很多。

图同构问题只是大框架下的一个问题而已。它也像因子分解问题一样，是NP问题中的一个，但是我们并不清楚它是不是属于P问题或者NP完全问题。

图非同构问题是AM中的代表问题，随机验证者通过向证明者提出一个问题以解决问题（Arthur–Merlin protocol）。AM中的图非同构问题暗示了图同构问题不像NP完全问题，也表明了在合理的去随机化的假设下，图非同构问题在NP中。Kobler，Schöning和Toran关于图同构的计算复杂问题写了一本书。

图同构中即使很小的进步都会掀起领域波澜。在80年后期的一个理论分会上，一个演讲者在提到有关于图同构是NP问题的证明（他并没有）时，造成了重大的轰动。Babai的宣称更是引起巨大反响，并且那些了解他的人也意识到，他不会在不确定有证据前做出那样的声明。这次演讲把从组合数学到图论的大量的想法集合在一起。我的感受是那些看了演讲但不相信证据的人至少会感到Babai确实找到了一些线索。

新智元注：什么是P和NP

在一个由问题构成的集合中，如果每个问题都存在多项式级复杂度的算法，这个集合就是 P 类问题（Polynomial）。这意味着，即使面对大规模数据，人们也能相对容易地得到一个解，比如将一组数排序。

“NP”的全称为“Nondeterministic Polynomial”，指的是能在多项式时间内检验一个解是否正确的问题。NP 类问题也等价为能在多项式时间内猜出一个解的问题，这里的“猜”指的是如果有解，那每次都能在很多种可能的选择中运气极佳地选择正确的一步。

如果 P=NP，会将数学转变为计算机对任何问题寻找拥有合理长度的证明学科，因为计算机能在一个多项式时间内验证一个证明是否正确。

图同构有什么应用？

1、密码破译，验证两个字符串是否等同

2、化学物质搜索：从庞大的数据库中，比对出这个化学物质是什么

3、文件比较

4、社交网络分析（社交网络就是一张大图）

5、基因图谱分析（基因是更大的一张图了）

......

有了Babai的重大突破的算法，内行现在会说图同构属于P问题了。素性测试从伪多项式时间到多项式时间花了几十年，恐怕图同构也不例外。但是，这些很可能发生，而且图同构问题的复杂性那时就会变得更简单。

几点想法：我能想起的重大突破都是被发表到论文上的，等着人们慢慢研习。这是我记忆中第一个以演讲形式呈现的重大突破。

另外，我们通常把理论认为是年轻人的游戏，大部分重大突破来自研究人员的早期学术生涯。Babai已经65岁了，他刚刚因为在交互式证明、群体算法和通信复杂性上的毕生研究获得了高德纳奖。Babai应用了他在组合数学和群论上的渊博的知识得到了他的算法。没有哪位年轻的研究者能够有像他一样的知识体系或者底蕴整合各个部分。