图同构在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应用了他在组合数学和群论上的渊博的知识得到了他的算法。没有哪位年轻的研究者能够有像他一样的知识体系或者底蕴整合各个部分。

原文发布于微信公众号 - 新智元(AI_era)

原文发表时间:2015-11-14

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏新智元

长尾有多长:人工智能先驱与分形之父的幂律之争

【新智元导读】因为在人工智能等方面的突破性研究荣获图灵奖的赫伯特·亚历山大·西蒙(Herbert Alexander Simon)曾就幂律及其产生机制的问题与被...

3066
来自专栏大数据文摘

考研数学崩了?再看他们是如何靠数学挣钱的!(内附原题及隐藏福利)

1333
来自专栏CDA数据分析师

警惕!机器学习入门阶段易犯的5个错误

怎样进入机器学习领域没有定式。我们的学习方式都有些许不同,学习的目标也因人而异。 但一个共同的目标就是要能尽快上手。如果这也是你的目标,那么这篇文章为你列举了程...

1685
来自专栏PPV课数据科学社区

如何看待「机器学习不需要数学,很多算法封装好了,调个包就行」这种说法?

编者按:这个问题放到更大的范围,也同样适用于回答“学习数据挖掘是否需要学好数学?”。作者从实践的几个方面给出了自己的理解,小遍认为还是比较好的回答了这个问题。 ...

3525
来自专栏数据科学与人工智能

【机器学习】什么是机器学习:一次权威定义之旅

在这篇文章中,我想要解决一个很简单的问题:机器学习是什么? 你可能对机器学习感兴趣或者稍稍了解。如果有一天你和朋友或同事聊起机器学习,那么一些人可能会问你“机...

1935
来自专栏AI研习社

如何看待「机器学习不需要数学,很多算法封装好了,调个包就行」这种说法?

不抖机灵,想从接触过机器学习学术圈但已投身工业界的角度来回答。 我认为:大部分机器学习从业者不需要过度的把时间精力放在数学上,而该用于熟悉不同算法的应用场景和掌...

34710
来自专栏窗户

再谈谈数学

  在一个很老的群里聊天,群里就那么二十几个人,都是搞这行的,在网上认识了十几年。一人是某大型电子地图公司出来的,说,”地图里面人工智能不就是用初中的概率论搞起...

1858
来自专栏量子位

斯坦福教授用新算法做药物研发,只需少量训练数据 | 论文+代码

李杉 李林 编译整理 量子位 报道 | 公众号 QbitAI 深度学习可以通过看脸认出不同的人,帮医生检查医疗影像识别病变,将语音转成文字……在各种领域,都有着...

2668
来自专栏大数据文摘

Nature新研究 | 科学家的职业巅峰可以被预测吗

1634
来自专栏镁客网

北大课题组改进ECC测序法,利用信息冗余大幅增加测序精度 | 黑科技

1170

扫描关注云+社区