能够被计算机解决的问题的特点是?

如题所述

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

○各种“复杂性类”(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完全问题
温馨提示:答案为网友推荐,仅供参考
第1个回答  2020-10-08
1、分析问题。

用电脑来解决问题时,首先电脑要对问题进行定性、定量的分析,然后才能设计算法。定性分析法是对问题进行“质”的方面的分析,确定问题的性质,定量分析法,是对要解决的问题的数量特征、数量关系与数量变化进行分析的方法。

2、设计算法。

算法(Algorithm)是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制。也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出。如果一个算法有缺陷,或不适合于某个问题,执行这个算法将不会解决这个问题。

不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

3、编写程序。

设计完算法后,就要使用某种程序设计语言编写程序代码,并最终得到相应结果。编程的语言包括汇编语言、机器语言和高级语言。高级语言中最简单、最常用的是Visual Basic语言和Pascal语言。

扩展资料:

人类解决问题:靠知识、见识、常识、经验、直觉、甚至赌博;

计算机解决问题:靠知识库、推理、推演、演绎、计算和预测以及概率分析。

人类会受外界因素和个人情感的干扰,导致同样的条件不同的结果;计算机则不受干扰,满足某个或某些条件,就会执行预先设定的命令。

利用计算机程序解决问题的基本过程:

了解利用计算机解决问题的基本过程。

了解问题分析与算法设计之间的关系。
相似回答