图同构在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 条评论
登录 后参与评论

相关文章

来自专栏新智元

邓侃解读谷歌首篇电子病历论文:完整披露谷歌医疗大脑野心

作者:邓侃 【新智元导读】上周,谷歌公布了首篇电子病历相关论文,由Jeff Dean率队联合众多大牛和顶级医学院完成。然而,不少业内人士,包括康奈尔大学副教授王...

3247
来自专栏机器之心

更偏好白人男性?Science新研究证明人工智能也能学会偏见

选自Science 机器之心编译 参与:吴攀、晏奇 至少从口号上来说,我们一直在追求「人人平等」,但我们也都清楚我们离这一目标还相去甚远,部分原因是因为世界并不...

3478
来自专栏量子位

我在谷歌大脑这一年

问耕 编译整理 量子位 出品 | 公众号 QbitAI ? 这篇文章的原作者是Colin Raffel。他2016年于哥伦比亚大学获得电子工程博士学位,随后入选...

3084
来自专栏安恒信息

安恒信息两篇核心AI异常检测论文入选IEEE DSC国际会议

6月18日-21日,“第三届IEEE网络空间数据科学国际会议”在广州召开。业界代表及专家齐聚一堂,并就网络空间数据科学的科研和前沿发展方向进行交流。而安恒信息的...

1274
来自专栏机器之心

深度 | 辛普森悖论:如何用同一数据证明相反的论点

想象一下,你和你的小伙伴正在努力寻找一个完美的餐厅,以便愉快的享用晚餐。我们清楚这个过程可能会花费数小时去争论,你会找到现代生活的便利之处:在线评论。通过在线评...

672
来自专栏AI科技评论

【深度】Nature:我们能打开人工智能的“黑箱”吗?

编者按:人工智能无处不在。但是在科学家信任人工智能之前,他们首先应该了解这些人工智能机器是如何运作的,这也就是文中所提到的“黑箱”问题。在控制论中,通常把所不知...

2966
来自专栏大数据文摘

视觉研究的前世今生(下)

2054
来自专栏机器之心

现场 | CVPR 2018第一天:精彩的Workshop与被中国团队进击的挑战赛

前伯克利 CS 系主任 Jitendra Malik:研究 SLAM 需要结合几何和语义

571
来自专栏吉浦迅科技

(图解)人工智能的黄金年代:机器学习

Lady我在整理一些关于Deep learning方面的学习资料,看到好文章总是忍不住想跟各位分享。这次将系统地介绍深度学习的前世今生,文章很有趣,但也很长,将...

37715
来自专栏大数据文摘

AI大事件 | Uber展示无人驾驶可视化工具,AI初创公司Appier获得3300万美元C轮融资

1853

扫码关注云+社区