2015年11月美著名数学家宣布解决图同构算法 打破30年僵局

baidu

2015年11月美著名数学家宣布解决图同构算法 打破30年僵局

一个被理论计算机科学家誉为突破性的算法诞生了。这个算法可以映射出当前复杂性理论(complexity theory)的深奥程度，并探索出计算问题(computational problems)究竟该如何解决。也就是2015年11月，芝加哥大学的数学和计算机科学教授László Babai(编者注：Babai是今年Knuth Prize得主)宣布他想出了一个新的解决“图同构”问题的算法 —— 这个问题在计算机科学中算得上是最诱人的奥秘。

Babai教授认为，他的新算法比以往算法的效率都要高，即使是曾经保持30多年记录的最佳算法。他的论文已经提交给美国计算机协会第48届计算理论会议，并已能在预印本文库arxiv.org上下载。

几十年来，图同构问题(graph isomorphism problem)在复杂性理论中享有特殊的地位。相比其他计算问题，人们很容易把它们分类成难或易，但图同构问题却无法做这样的分类。它似乎比容易的问题更困难，但比困难的问题更容易，就像落入两者间的一块无人之境。它是这块灰色地带里最著名的两个问题之一。麻省理工学院的复杂性理论学家Scott Aaronson教授评论说：“现在看来，另一个可能要一枝独秀了”。Babai教授的工作的确刺激了理论计算机科学家。正如圣菲研究所(Santa Fe Institute.)的计算机科学家Joshua Grochow所说：“如果他的研究正确，那么即便不是近几十年，也是近十年中的大成就了。”

图同构算法

图同构

计算机科学家使用“图”(graph)这个词来指代一种网络，这种网络是由若干给定的点及连接两点的线所构成的。简单来说，图的同构问题是：如何判断两张图是否是同样的图。也就是说，两个图的点是 一一 对应(即“同构”)，维持相同的节点连接方式。这个问题很容易表述，但很难解决。因为即使是很小的图，只要通过移动节点的位置，就可以使其看起来完全不同。

现在，问题的难度水平好像降低了，而Babai教授的工作为此作出了重要的一步，即通过他所阐述的“准多项式时间”(quasi-polynomial-time)算法来解决。正如Aaronson教授所描述，这个算法把图同构问题放到了P类问题的“大都市圈”内(译者注：P类问题指存在多项式级复杂度算法的问题，见下文)，于是就可以用经典的办法有效地解决它。虽然这项新工作还不至于为困难的图同构问题画上句号，但许多研究者把它视作一种游戏规则的改变。对此，Grochow评论道：“在他发表之前，我认为除了他自己，任何人都会觉得这个问题无法在未来10年内解决，甚至永远解决不了。”

最近几周，Babai已经作了4次讲座，对学者们陈述他的算法，然而在其他专家对他的新论文审查通过前还尚需时日。所以Babai拒绝向媒体发言，他在一封电子邮件中写道：“科学的完整性要求我：新结果必须在对媒体公开前通过同行专家彻底的审查。”

其他研究人员倒是谨慎又乐观地认为：他的证明将取得成功。“Babai有很好的声誉”，Aaronson教授说，“他是名副其实地值得信赖。”

来自加州大学伯克利分校的计算机科学家Luca Trevisan也在Babai的第二次讲座之后评论说：“我们对此都很乐观。假定证明是正确的，那就是一个标志性的成果。”

盲测

如何对给定的2个图，检查它们是否同构?

一种方法是：简单地去比较每一个点来匹配另一个图中可能对应的所有节点。但一张具有n个节点的图，如此匹配的计算数量就为n的阶乘(1 * 2 * 3 *…* N)，远远超过n的数量级。这种比蛮力的方法非常不切实际，只适用于极少节点的图。假如图里只有10个节点，也已经需要300多万次可能的匹配检查。对于100个节点的图，可能的匹配数大概会远远超过可见宇宙中的原子数。

一般计算机科学家们认为，一个算法若能有效率，其运行时间必须是一个多项式而不是阶乘，如n的二次方或三次方;毕竟多项式的增长比起阶乘或指数函数(2的n次方)来要慢得多。所以能用多项式时间解决的算法问题被统称为P类问题。自这个分类首次在几十年前提出，已经有数千个自然科学和工程领域的问题被证明归于此类。

计算机科学家认为，P类问题是相对容易的问题，而另一个类别里的数千个问题则比较难，即“NP完全”问题(NP-complete)。从来没有人为NP完全问题找到过一个有效的算法，大多数计算科学家甚至认为没有人会找到。于是，在数学上，“NP完全问题是否真的比P类问题更难”则成了价值百万美金的P vs NP问题，也被广泛认为是最重要的问题之一。

图同构问题既不是已知的P问题，也不是已知的NP完全问题。其实，它似乎徘徊在这两者之间。它就好像在自然问题里占据了唯一的小块灰色边缘之境；而唯一和它并肩齐名的问题是素数分解问题(分解质因数)。如Grochow所言：“很多人都会花时间在图同构问题上，因为它说起来是一个非常自然的、简单的问题，却又是那么神秘。”

本来，人们有充分的理由怀疑图同构是NP完全问题。但是，它有一个奇怪的属性，一个其他NP完全问题没有的属性：在理论上，它是可能有解的。比如，一个无所不知的人(以下用“梅林”代称)要让一个普通人(以下用“亚瑟”代称)相信，两张图是不同的。即便他没有给出任何差异之处的提示，普通人却也能分辨出来。

这种“零知识”证明类似于，梅林要说明可口可乐和百事可乐有不同的配方，而亚瑟不了解它们之间的差异。于是梅林给亚瑟反复地盲测，如果亚瑟能始终正确识别可口可乐和百事可乐的味道，那么他也会接受这两种饮料是不同的。

同样，如果梅林告诉亚瑟，2个图是不同的，亚瑟也就用盲测来验证这个说法。亚瑟把两个图形遮起来，然后移动它们各自的节点，使它们看起来与初始的样子不同。然后再拿给梅林问他，哪一张是哪一张。如果这两者是同构的，梅林就无法回答。但如果梅林一次又一次地能答对这些问题，亚瑟就会得出结论：两张图肯定是不同的，即使他自己不能发现其中的差异。

从来没有人发现用一个盲测就能解决任何一个NP完全问题。鉴于这个以及其他的原因，理论计算科学家们达成了一个普遍的共识：图同构可能不是NP完全问题。

而对于反向的问题 —— 图同构是否属于P类问题 —— 的证据则更混杂。一方面，实践中的图同构算法不能有效地解决这个问题。而几乎所有图，你都能找到可行的算法，甚至你能随机选择算法。计算机科学家们不得不努力工作来从中纠错。

另一方面，图同构也被计算机科学家称为“普遍级”的问题。任何涉及到两种“组合结构”是否同构的问题都和图同构相关。比如：两张不同的数独游戏，是否是同一道益智问题 —— 这些都可以改写为图同构问题。这意味着如果有一个图同构的快速算法将一次性解决所有这些问题。Grochow说：“通常当一个问题有这样的普遍性，它也就意味着一种困难”。

2012年，马里兰大学的计算机科学家，William Gasarch曾对图同构问题有过一次非正式的调查。他发现，在他调查的理论计算机科学家中，有14人认为这属于P类问题，而6人认为它不是。在Babai发表之前，很多人都没想到这个问题能在短期内解决。比如Grochow认为它不是P问题，也可能是P问题，总之在有生之年，他都不一定会知道。

用数字作图

Babai提出的算法并没有把图同构全部带入P类问题，但它已经很接近了。它被称为准多项式，他断言，这意味着一张有n个节点的图，其算法的运行时间虽然不具有n的恒定增长率(如多项式中的那样)，但可以类比成同样缓慢的增长率。

曾经对图同构最好的算法是由Babai和Eugene Luks(如今俄勒冈大学的名誉教授)在1983年一起参与创立的。它的运行速度为“次指数”时间。其运行时间与新算法“准多项式”之间的差距，就相当于指数到多项式速度的差距。Babai教授从1977年起一直在图同构问题上工作至今，“他琢磨这个问题大约已经有40年”，Aaronson对此非常了解。

Babai的新算法是以第一张图的一些小节点开始，实际会给它们每一个点“画”上不同的颜色。然后，它假设第二张图里有其一 一对应的点，开始在其中寻找同构，并在找到后将这些对应节点标上相同的颜色。该算法循环往复直到最终验证完所有可能的猜测。

一旦初始猜测正确的被涂好颜色，那么它就限制了其他节点的连接。例如，在第一张图里有个蓝色节点，那么与其连接的另一个未标注颜色的节点在第二个图里也必须对应于一个与蓝色节点连接的点。为了追踪这些条件，该算法就会引入新的颜色并标注：比如若该点被链接到1个蓝色点和1个红色点则标为黄色，或者若它有连接到1个红色节点2个黄色点则标为绿色，等等。该算法会不断引入更多的颜色，直到没有其余的连接特征供其捕捉。

一旦图变成彩色的，该算法就可以依据节点中不同的颜色去排除所有的匹配。如果算法足够幸运，整个绘画的过程就能将图分成许多不同颜色区块，这就大大减少了一些算法必须考虑的可能同构数目。如果情况相反，大部分节点的颜色相同，那么就采用Babai开发的另一种不同方式来减少可能的同构数。除了一种情况作为例外：即两图都包含“约翰逊图式”的相关结构时。因为约翰逊图包含有太多的对称性，使得涂点的过程和Babai的进一步改进尚不足以对该算法提供指导。

高度对称的“约翰逊图”是他的算法方案里没有涵盖的唯一案例

高度对称的“约翰逊图”是他的算法方案里没有涵盖的唯一案例

2015年11月10日，在新算法的第一次讲座上，Babai称这些“约翰逊图”对致力于用涂点方案解决图同构问题的计算机科学家们来说是“无法形容的痛苦之源”。但约翰逊图可以通过其他算法比较容易地处理，所以即便这些图是他涂点方案的唯一障碍，Babai也能够驯服它们。

“他的做法是一个非常符合自然的策略，而且在某种意义上说非常明快”，芝加哥大学的计算机科学家，Janos Simon评论Babai的方案时说，“这很可能是正确的，只是所有数学家都很谨慎。”

虽然新的算法已经把图同构问题比以往更拉向P类问题，但Babai在他的第一次讲座里猜测，图同构问题可能在P类问题的边界 —— 即在郊区而不是城市中心。Trevisan说这的确是最有趣的可能性，因为它会使图同构这样的第一自然问题有个拟多项式的算法，但没有多项式的算法。他说：“这就表明，复杂性理论的领域远比我们想象的要丰富得多”。然而，即便此话当真，也不要指望很快就有证据出现：用以证明它将能大量解决P与NP的问题。因为，这个算法只意味着把图同构从NP完全问题中分离出P类问题。

事实上，许多计算机科学家相信，图同构正进入一条推进轨道，最终滑入P类问题。Trevisan认为，这是常见的趋势，一旦一个拟多项式算法被发现，大家就会这样预测，等待再一次的突破。他说：“总之，这个问题已经带给我们不少惊讶了，但也许还会有更多的惊喜即将到来。”

版权声明：
本文由 德云社区 整理，原文来自网络。