保存网页视频-手机怎么上网
2023年4月3日发(作者:win8正式版密钥)
NP完全的问题
一个NP-完全的问题具有如下性质:它可以在多项式时间内求解,当且仅当所有的其他的NP-完
全问题也可以在多项式时间内求解。P是所有可在多项式时间内用确定算法求解的判定问题的集合。NP
问题是所有可用多项式时间算法验证其猜测准确性的问题的集合。
令L1和L2是两个问题,如果有一确定的多项式时间算法求解L1,而这个算法使用了一个在多项式
时间内求解L2的确定算法,则称L1约化为L2。如果可满足性约化为一个问题L,则称L问题是NP-
难度的。如果L是NP难度的且L(-NP,则称L是NP-完全的。NP并不是NON-POLYNOMIAL,
把NP说成是NON-POLYNOMIAL,是望文生义,读书不求甚解。事实上,如果你能够证明某个NP问
题是个NON-POLYNOMIAL的问题,你就可以去领那七个百万美元数学大奖中间的一个了。数学上著
名的NP问题,完整的叫法是NP完全问题,也即“NPCOMPLETE”问题,简单的写法,是NP=P?的
问题。问题就在这个问号上,到底是NP等于P,还是NP不等于P。证明其中之一,便可以拿百万美元
大奖。这个奖还没有人拿到,也就是说,NP问题到底是Polynomial,还是Non-Polynomial,尚无定论。
NP里面的N,不是Non-Polynomial的N,是Non-Deterministic,P代表Polynomial倒是对的。NP就是
Non-deterministicPolynomial的问题,也即是多项式复杂程度的非确定性问题。
如果一个判定性问题的复杂度是该问题的一个实例规模n的多项式函数,则这种可以在多项式时间
内解决的判定性问题属于P类问题。P类问题就是所有复杂度为多项式时间的问题的集合。通俗地称所
有复杂度为多项式时间的问题为易解的问题类,否则为难解的问题。
有些问题很难找到多项式时间的算法(或许根本不存在),例如“找出无向图中哈米尔顿回路”问题。
但如果给了该问题的一个答案,可以在多项式时间内判断这个答案是否正确。例如说对于哈米尔顿回路
问题,给一个任意的回路,很容易判断它是否是哈米尔顿回路(只要看是不是所有的顶点都在回路中
就可以了)。这种可以在多项式时间内验证一个解是否正确的问题成为NP问题,亦称为验证问题类。
简单的说,存在多项式时间的算法的一类问题,称之为P类问题;而像梵塔问题,推销员旅行问题
等问题,至今没有找到多项式时间算法解的一类问题,称之为NP问题。同时,P类问题是NP问题的一
个子集。
非确定性问题的概述
什么是非确定性问题呢?有些计算问题是确定性的,比如加减乘除之类,你只要按照公式推导,
按部就班一步步来,就可以得到结果。但是,有些问题是无法按部就班直接地计算出来。比如,找大
质数的问题。有没有一个公式,你一套公式,就可以一步步推算出来,下一个质数应该是多少呢?这样
的公式是没有的。再比如,大的合数分解质因数的问题,有没有一个公式,把合数代进去,就直接可
以算出,它的因子各自是多少?也没有这样的公式。这种问题的答案,是无法直接计算得到的,只能通
过间接的“猜算”来得到结果。这也就是非确定性问题。而这些问题的通常有个算法,它不能直接告诉你
答案是什么,但可以告诉你,某个可能的结果是正确的答案还是错误的。这个可以告诉你“猜算”的答案
正确与否的算法,假如可以在多项式时间内算出来,就叫做多项式非确定性问题。而如果这个问题的所
有可能答案,都是可以在多项式时间内进行正确与否的验算的话,就叫完全多项式非确定问题。完全
多项式非确定性问题可以用穷举法得到答案,一个个检验下去,最终便能得到结果。但是这样算法的
复杂程度,是指数关系,因此计算的时间随问题的复杂程度成指数的增长,很快便变得不可计算了。
人们发现,所有的完全多项式非确定性问题,都可以转换为一类叫做满足性问题的逻辑运算问题。
既然这类问题的所有可能答案,都可以在多项式时间内计算,人们於是就猜想,是否这类问题,存在
一个确定性算法,可以在指数时间内,直接算出或是搜寻出正确的答案呢?这就是著名的NP=P?的猜
想。解决这个猜想,无非两种可能,一种是找到一个这样的算法,只要针对某个特定NP完全问题找到
一个算法,所有这类问题都可以迎刃而解了,因为他们可以转化为同一个问题。另外的一种可能,就
是这样的算法是不存在的。那么就要从数学理论上证明它为什么不存在。
有些看来好像是非多项式的问题,其实是多项式问题,只是人们一时还不知道它的多项式解而已。
NP-hard
其中,NP是指非确定性多项式(non-deterministicpolynomial,缩写NP)。所谓的非确定性是指,
可用一定数量的运算去解决多项式时间内可解决的问题。NP问题通俗来说是其解的正确性能够被“很容
易检查”的问题,这里“很容易检查”指的是存在一个多项式检查算法。相应的,若NP中所有问题到某一
个问题是图灵可归约的,则该问题为NP困难问题
例如,著名的推销员旅行问题(TravelSalemanProblemorTSP):假设一个推销员需要从香港出发,
经过广州,北京,上海,…,等n个城市,最后返回香港。任意两个城市之间都有飞机直达,但票
价不等。现在假设公司只给报销C元钱,问是否存在一个行程安排,使得他能遍历所有城市,而且总
的路费小于C?
推销员旅行问题显然是NP的。因为如果你任意给出一个行程安排,可以很容易算出旅行总开销。
但是,要想知道一条总路费小于C的行程是否存在,在最坏情况下,必须检查所有可能的旅行安排!这
将是个天文数字。
旅行推销员问题是数图论中最著名的问题之一,即“已给一个n个点的完全图,每条边都有一个长
度,求总长度最短的经过每个顶点正好一次的封闭回路”。Edmonds,Cook和Karp等人发现,这批难题
有一个值得注意的性质,对其中一个问题存在有效算法时,每个问题都会有有效算法。
迄今为止,这类问题中没有一个找到有效算法。目前倾向于接受NP完全问题(NP-Complet或NPC)
和NP难题(NP-Hard或NPH)不存在有效算法这一猜想,认为这类问题的大型实例不能用精确算法求
解,必须寻求这类问题的有效的近似算法。
此类问题中,经典的还有子集和问题;Hamilton回路问题;最大团问题
形式化定义
目前常用的定义是所谓的“关系定义式”。即对于一个语言L,L在NP中,那么存在多项式时间图灵
机M,和多项式p使得
扩展阅读:
多项式时间(Polynomialtime)在计算复杂度理论中,指的是一个问题的计算时间m(n)不大于问题
大小n的多项式倍数。任何抽象机器都拥有一复杂度类,此类包括可于此机器以多项式时间求解的问题。
更多推荐
多项式时间
发布评论