孙鹏审校原理来源仔仔编译

复杂问题的简单指南

本文经授权转载自微信公众平台原理(ID:principia1687),未经授权禁止二次转载。

计算机能够做什么?又有哪些问题计算机几乎不可能解决?这些问题构成了计算复杂度的核心。这里,我们呈现了一张关于计算复杂度的地图:

○ 各种“复杂性类”(complexity class)将问题排序为层级结构:一个类可能包含另一个类的所有问题,以及其他需要额外计算资源的问题。

一个问题从本质上来说能有多难?这是计算机科学家的基本任务,他们希望将问题归类到所谓的复杂性类(complexity class)中。复杂性类包含所需计算资源少于一定数量的所有计算问题,这种计算资源通常指时间或内存。

以一个非常大的数字123456789001为例,一个问题可能会是:这个数字是质数、也就是只能被1和它自己整除吗?计算机科学家可以用快速算法(fast algorithm)解决这个问题,这种算法不会因为数字变得任意大而陷入停顿。对于123456789001这个例子,答案是它并不是质数。

然后我们可能会问:这个数字的质因数是什么?对于这个问题,并不存在第一个问题中的快速算法——除非使用量子计算机。因此,计算机科学家认为这两个问题属于不同的复杂性类。

存在许多不同的复杂性类,尽管大多数情况下,研究者还不能证明一个类完全区别于其他类。证明这些分类间的区别是该领域最困难和最重要的开放性问题之一,这就是为什么五月底Ran Raz和Avishay Tal这两位计算机科学家的证明结果被认为是如此重要。他们解决了科学家们自1993年就开始寻求答案的问题,证明了存在一些只有量子计算机能够解决、而无论现在或未来的经典计算机都永远不可能解决的问题,也就表明了量子计算机和经典计算机的两个复杂性类确实不同。(进一步阅读《误解带来的乐观与恐慌》

复杂性类之间的差异可以是微妙的,也可以是明显的,如何正确分类是一个挑战。因此,我们将介绍以下10个基本的复杂性类作为一个入门,希望你看完后再也不会混淆BPP和BQP了。


P

代表:多项式时间(Polynomial time)


简单介绍:经典(非量子)计算机能够轻易解决的所有问题。

详细介绍:P类的算法必须在多项式时间 t=n^c 内停止并输出正确的结果,其中n是输入的长度,c是常数。

典型问题:

  • 一个数是质数吗?

  • 两点之间的最短路径是什么?


NP

代表:非确定性多项式时间(Nondeterministic Polynomial time)


简单介绍:只要给出一个解,经典计算机就能够快速验证给出的解是否正确的所有问题。

详细介绍:如果给定“是”的答案,可在多项式时间内确定这个答案是正确的,这就是一个NP问题。如果输入是一个字符串X,需要判断答案是否为“是”,那么这个简短的证明将是另一个字符串Y,然后,在多项式时间内,Y被用来验证答案是否为“是”。(Y有时被称为“短时见证”(short witness),NP类的所有问题都有“短时见证”,这些“短时见证”使得问题能够迅速被解决。)

典型问题:

  • 分团问题(Clique problem)

想象一个有边和节点的图形,例如Facebook的社交网络图,其中节点是个人,如果两个人建立好友关系,两个节点就被一条边连接。小团体(Clique)是整个图形的一个子集,其中每一个人都是其他人的朋友,也就是其中任意两个节点彼此连接。有人或许会问:存在20个人的小团体吗?50个人呢?100个人呢?寻找这样的小团体是图论领域的一个“NP完全”(NP-complete)问题,NP完全意味着这是NP类问题中最复杂的一种。然而,如果给出了一个潜在的答案,比如说50个节点可以或不可以形成一个小团体,那么问题就迎刃而解了。

○ 6个节点的网络图中大小为3的小团体。来源 | Wikepedia

  • 最短路径问题(Travelling salesman problem)

考虑一系列城市,其中每一对城市之间的距离是已知的,有没有一种方法能够以最短的距离穿越所有的城市呢?例如,一个旅行推销员能够穿越美国各个州的首府,而将行程控制在11000英里内吗?(进一步阅读:《一位旅行家》

○ 最短路径问题。来源 | Wikepedia


NP-Complete


代表:NP 完全

简单介绍:在多项式时间内,所有NP类问题都能够被规约到的问题的集合。

详细介绍:在多项式时间内,如果所有NP类问题都能被转化为另一个NP问题,那么这个转化后的NP类问题就称为NP完全问题。NP完全问题满足两个条件:1. 本身是NP类问题。2. 所有NP类问题都能规约到该问题。

典型问题:

  • 给一个整数集合,证明是否存在一个非空子集,使得该集合内的数字和为0。


NP-Hard

代表:NP困难


简单介绍:在多项式时间内,能够被规约到该问题的所有问题。

详细介绍:在多项式时间内,如果所有问题都能被转化为另一个问题,那么这个转化后的问题就称为NP困难问题。它满足NP完全问题的第二个条件,但不一定要满足第一条,即NP困难问题未必能在多项式时间内验证。

典型问题:

○ 左侧是在假定P≠NP的前提下,P,NP,NP-Complete与NP-Hard四个复杂性类的关系,右侧则是假定P=NP的前提下它们的关系。 | 来源 Wikipedia


PH

代表:多项式层级结构(Polynomial Hierarchy)


简单介绍:PH是NP的外推,它包含NP类的所有问题,并在NP类问题的基础上,添加了额外的复杂度。

详细介绍:PH类包含一些交替使用比如“存在”、“每一个”、“所有”等“量词”(quantifier)的问题,使NP类问题更加复杂。一个关于交替量词问题的例子是:给定X,是否存在这样的Y,使得对于每一个Z,都存在这样的W,使得R成立?一个问题包含的量词越多,它就越是复杂,在多项式层级结构中的排序也就越高。

典型问题:

  • 确定是否存在规模为50的小团体,但不存在规模为51的小团体。


BPP

代表:有限错误概率多项式时间(Bounded-error Probabilistic Polynomial time)


简单介绍:在多项式时间内,可以通过包含随机性元素的算法快速解决,且通常输出结果的错误概率小于1/3的问题。

详细介绍:BPP与P唯一不同的是,BPP的算法允许包含随机决策的步骤。BPP的算法只需要以接近1的概率给出正确答案即可。

典型问题:

  • 给定两个不同的公式,每个公式产生一个包含很多变量的多项式,这两个公式计算的是相同的多项式吗?这个问题叫做多项式恒等检验问题。

研究人员想知道的是:BPP=P是否成立。如果这是真的,那就意味着每一个随机性算法都可以去随机化。他们相信这是事实,因为对于每一个存在有效随机性算法的问题,都有一个有效的确定性算法,但他们还不能证明这一点。

BQP

代表:有限错误量子多项式时间(Bounded-error Quantum Polynomial time)

简单介绍:在多项式时间内,量子计算机能够轻易解决的所有问题。

详细介绍:在多项式时间内,量子计算机能够轻易解决,且错误机率小于1/3的所有问题。

典型问题:

  • 确定一个整数的质因数。

计算机科学家已经证明:PSPACE包含BQP,且BQP包含P。关于BQP和NP这两个类的关系,有一些问题属于NP类,而不属于BQP类,反之亦然,两者互不包含。

○ 计算复杂度地图上一块新区域:上文提到的五月底的研究,证明了存在属于BQP,却不属于PH的问题。(注:P-经典计算机能够快速解决的问题;NP-经典计算机就能够验证正确性的问题;NPC-NP完全问题;BQP-量子计算机能够有效决的问题。)


QMA

代表:量子梅林亚瑟(Quantum Merlin Arthur)


简单介绍:量子计算下的NP类问题。

详细介绍:在量子计算下,如果给定 “是”的答案,在多项式时间内,能够完成验证,确定这个答案正确与否,这就是QMA类问题。QMA类问题相对于BQP类问题的关系,就相当于NP类问题相对于P类问题,也就是验证与求解的复杂度的区别。

典型问题:

局部哈密顿量问题。


PSPACE

代表:多项式空间(Polynomial Space)


简单介绍:PSPACE包含了所有只要用合理大小的内存(多项式量级的内存)就能解决的问题。

详细介绍:在PSPACE中,我们不关心时间,只关心运行算法所需的内存。

典型问题:

  • P、NP和PH类的所有问题都包含在PSPACE中。

计算机科学家已经证明,PSPACE包含PH,PH包含NP,NP包含P。然而,对于P是否等于NP,是否等于PH,是否等于PSPACE,计算机科学家始终一筹莫展。P=NP问题是克雷数学研究所发布的七道难题之一,可以进一步阅读《一个价值百万美金的问题》了解更多。


EXPTIME

代表:指数时间(EXPonential Time)


简单介绍:在指数时间内,经典计算机能够解决的所有问题。

详细介绍:EXP包含之前所有的类——P、NP、PH、PSPACE、BQP和QMA等。研究人员已经证明,EXP不同于P,他们在EXP中发现了不属于P的问题。

典型问题:

  • 国际象棋和跳棋之类的游戏都属于EXP。如果棋盘可以是任意大小的,那么在给定的棋局形势下,确定哪一个棋手具有优势就是一个EXP问题。

计算机科学家想要证明PSPACE不包含EXP。他们认为EXP中有一些问题不包含在PSPACE中,因为有时候EXP类问题的解决需要大量的内存。计算机科学家知道如何区分EXP和P。

在计算复杂度的地图上,科学家们已经证明与尚未证明的问题可以总结如下:

从中可见,问题的源头主要在于那个价值百万美金的问题:P=NP是否成立。P是否等价NP的问题,可以简化为NP完全问题的证明,也就是证明,是否能用多项式级复杂度的算法来解决任何一个NP完全问题。

参考链接: https://www.quantamagazine.org/a-short-guide-to-hard-problems-20180716/ 

原文链接:https://mp.weixin.qq.com/s/SaiB3DNWA-ofmo8chykXZQ

理论量子计算数学
2
相关数据
哈密顿人物

William Rowan Hamilton爵士MRIA(1805年8月4日 - 1865年9月2日)是一位爱尔兰数学家,他为经典力学、光学和代数做出了重要贡献。 虽然哈密顿不是物理学家(他认为自己是一个纯粹的数学家)他的工作对物理学起着至关重要的作用,特别是他对牛顿力学的重新定义,现在称为哈密顿力学。 这项工作已被证明是对电磁学等经典场论的现代研究以及量子力学发展的核心。 在纯数学中,他最出名的是四元数的发明者。

逻辑技术

人工智能领域用逻辑来理解智能推理问题;它可以提供用于分析编程语言的技术,也可用作分析、表征知识或编程的工具。目前人们常用的逻辑分支有命题逻辑(Propositional Logic )以及一阶逻辑(FOL)等谓词逻辑。

图论技术

图论是以“图”为研究对象的一个数学分支,是组合数学和离散数学的重要组成部分。图是用来对对象之间的成对关系建模的数学结构,由“顶点”(又称“节点”或“点”)以及连接这些顶点的“边”(又称“弧”或“线”)组成。值得注意的是,图的顶点集合不能为空,但边的集合可以为空。图可能是无向的,这意味着图中的边在连接顶点时无需区分方向。否则,称图是有向的。

暂无评论
暂无评论~