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

相关文章

来自专栏机器人网

杜克大学研究让机器人拥有真正的3D视觉

为了让机器人能够胜任更复杂的工作,机器人不但要有更好的控制系统,还需要能更多地感知环境的变化。如今的机器人可以深入核电站进行调查、清理海洋石油泄漏、组建无人军队...

3704
来自专栏AI科技大本营的专栏

特朗普“模仿”奥巴马?进阶版换脸技术DeepFakes来了

DeepFakes,这种能够移花接木的技术,它能将图像或视频中把一张脸替换成另一张脸。

1212
来自专栏华章科技

机器学习进阶路上的五个境界

关于机器学习,这个话题最近实在太火了,甚至有些虚火了。有了虚火,就容易有泡沫。大浪淘沙,要想在数据科学这个行业生存下来,任何一个从业者都需要认清自己的位置,每上...

913
来自专栏AI研习社

博客 | 一份中外结合的 Machine Learning 自学计划

看了Siraj Raval的3个月学习机器学习计划的视频,感觉非常好,地址:https://www.youtube.com/watch?v=Cr6VqTRO1v...

671
来自专栏数据派THU

【独家】微软郑宇:大数据驱动智能城市讲座精华(附PPT)

[导读]本文整理自微软亚洲研究院“城市计算”领域负责人郑宇博士近期在清华大数据讲座上的分享内容。郑宇主持研发的Urban Air首次利用大数据来监测和预报细粒度...

2738
来自专栏AI研习社

读了这些书,才能正确入门深度学习

编者按:本文作者为 Jeffries Consulting 创始人 Daniel Jeffries,他以自己的阅读体验,对当前含金量极高的几本深度学习书籍进行点...

2836
来自专栏新智元

【谷歌草绘RNN瞄准超级AI】源自壁画的飞跃,AI 学会归纳抽象概念

【新智元导读】人类自从开始在洞穴的岩壁上画出简单的草图,认知能力就产生了飞跃——归纳抽象的能力大大提高。现在,谷歌的 Magenta 项目也在致力于这一研究。名...

3129
来自专栏机器之心

讨论 | Reddit热门话题:你是否也对NLP的现状感到失望?

3506
来自专栏大数据文摘

DeepMind早就不再下围棋了,新论文训练AI进行逻辑推理

1213
来自专栏人工智能头条

如何用3个月零基础入门机器学习?

1965

扫码关注云+社区