导读:
当我们遇到一个问题时,我们总是很自然的开始恩考求解这个问题的算法.我们大多数人都没有注意到问题本身的可解性.其实很多问题很难想出一种有效算法的,当然,遍历算法除外.如果我们有一台超强的计算机,那么一切算法都是没有意义的,因为一切问题都可以用遍历来解.
算法的效率其实正是体现在问题的大规模输入上,所以,我们在比较算法的好坏时,通常考虑它在大规模输入时的运行时间,占用空间等.P与NP问题正是源自算法执行的效率.
我想绝大多数学计算机的人都听过P与NP问题,但我觉得,真正能说出它是怎么回事的,不在多数.至少在我仔细看资料之前,我是说不出P与NP问题到底是怎么回事,以及怎么证明一个问题是NP或NP完全的.所以,我想写一些自己对P与NP问题的理解.
在介绍P与NP之前,我想先介绍两个概念.
1.确定性算法
设A是求解问题B的一个算法,如果在展示问题B的一个实例时,在整个执行过程中每一步都只有一个选择,则称A是确定性算法.因此如果对于同样的输入,实例一遍又一遍地执行,它的输出从不改变.
通常我们在写程序时,用到的都是一些确定性算法,比如说排序算法,最优化算法等.
2.不确定性算法
一个不确定性算法由下列两个阶段组成.
猜测阶段:在这个阶段产生一个任意字任串Y,它可能对应于输入实例的一个解,也可以不对应解.事实上,它甚至可能不是所求解的合适形式,它可能在不确定性算法的不同次运行中不同.它仅仅要求在多项式步数内产生这个串.
验证阶段:在这个阶段,一个确定性算全证两件事.首先,它检查产生的解串Y是否有合适的形式,如果不是,则算法停下并回答NO;另一方面,如果Y是合适形式,那么算法继续检查它是否是问题实例X的解,如果它确实是实例X的解,那么它停下并且回答YES,否则它停下并回答NO.我们也要求这个阶段在多项式步数内完成.
可能很多人会认为随机算法是一种不确定性算法.其实随机算法也是一种确定性算法,因为它的随机性也是通过在输入中加入一个用于产生随机值的串实现的,同样的串得到的随机值相同.
下面给出P与NP的定义:
P是一个判定问题类,这些问题可以用一个确定性算法在多项式时间内判定或解出;
NP是一个判定问题类,这些问题可以用一个确定算法在多项式时间内检查或验证出它们的解;
P事实上很直观,我们通常在编程中求解的问题大多都是P类问题.比如说排序,找最短路径等.NP这
个类事实上也很有趣,它并不要求给出一个算法来求解问题本身,而只是要求给出一个确定性算法在多项式时间内验证它的解.
NP完全问题
NP完全事实上表求NP中判定问题的一个子类.这类问题也是很有趣的,即如果它们中的一个被证明
是多项式时间内确定性算法可解,那么所有属于这一类的其它问题也是多项式时间内确定性算法可解.
多项式时间归约:
设A和B是两个判定问题.如果存在一个确定性算法C,它的行为如下:当给C展示问题A的一个实例时,算法A可以把这个实例变换成问题B的一个实例,使得A的实例跟B的实例有相同的YES/NO应答,并且这个变换在多项式时间内完成.那么我们说A多项式时间归约到B.
事实上,我们可以将多项式时间归约看做是一个函数的映射,即F(A)=B.并且这个F是多项式时间内可计算的.也就是说问题A实现上可以通过它自身满足的条件,通过一些形式上的改变而变换到问题B.形象地讲,问题A事实上不比B难,而问题B也同样不比问题A难.
NP困难与NP完全
一个判定问题A称为是NP困难的,如果对于NP中的每个问题B,B多项式时间归约到A.
一个判定问题A称为是NP完全的,如果对于NP中的每个问题B,B多项式时间归约到A,并且A在NP类中.
NP完全问题的证明:
要证明一个判定问题是NP完全的,只要在NP完全类中找到一个问题A,将这个问题归约到待证明问题即可.要证明问题是NP完全是很困难的,因为很多问题之间的转化过程是很难想到的.第一个被证明的NP完全问题是可满足性问题,它是判定一个合取范式的布尔公式F是否存在真值指派的问题.在很多NP完全问题的证明中,我们都可以用这个问题来归约,这里不再详述.
Trackback: http://tb.blog.csdn.net/TrackBack.aspx?PostId=754255
本文转自
http://blog.csdn.net/dansin/archive/2006/05/25/754255.aspx
分享到:
相关推荐
对p和np问题的简单介绍 对p和np问题的简单介绍 对p和np问题的简单介绍
P和NP问题,如果一个问题能用多项式时间复杂性的算法求解,那么就叫做P(英文多项式polynomial的第一个字母)问题。
本文档从定义入手介绍了P问题,NP问题,NPC问题,并举例来说明属于哪类问题,还有分析了它们之间的关系。
关于NP问题和P问题的比较和联系
关于P是否等于NP是一个存在了很久的问题,这里不做讨论。 通俗的理解这两个问题的话:在借助计算机的前提下。P问题很容易求解;NP问题不容易求解,但对于某一答案我们可以很快验证这个答案是否正确。 3.NPH...
这个问题,作为理论计算机科学的核心问题,其声名早已经超越了这个领域。它是Clay研究所的七个百万美元大奖问题之一,在2006国际数学家大会上,它是某个1小时讲座的主题。
在计算复杂性理论中,旅行商问题是NP类中的典型问题。 借助一种名为“最大删除法”的全新方法,为其构造了一... 由于这个问题也是NP完全的,因此必然证明P = NP是正确的。 它表明了著名的“ P vs NP”开放问题的破解。
Pvs_NP问题研究状态及其对密码学的意义
[总结]算法中的P问题、NP问题、NP完全问题和NP难问题 - CSDN博客.html
P问题与NP问题的关系 定理5.P⊆NPP \subseteq NPP⊆NP. 即,所有的P问题都是NP问题。当一个问题是P问题时,我们可以在多项式时间内求出问题的解。若要验证一个解(记为t1)是否正确时,只需使用多项式时间求解出这个...
P问题、NP难问题详解 总结: 定义:同时满足下面两个条件的问题就是NPC问题。首先,它得是一个NP问题;然后,所有的NP问题都可以约化到它。 证明:先证明它至少是一个NP问题,再证明其中一个已知的NPC问题能约化...
这个应该是全的,但好象是6寸的,网上没找到其他资源,只有这一种了。
NP完全问题(NP-C问题),是世界七大数学难题之一。 NP的英文全称是Non-deterministic Polynomial的问题,即多项式复杂程度的非确定性问题。...,问题就在这个问号上,到底是NP等于P,还是NP不等于P。
详细描述什么是NP、NPC、P问题。让你彻底理解计算机中的经典问题。
P不等于NP的证明,惠普研究员 论文草稿
P vs NP是克莱研究所的千禧年难题大奖中宣布的7道数学世纪难题中的一道。有人号称证明了该问题。感兴趣的可以阅读论文。
NP完全问题的概述,包括P类、NP类、CNP类问题的介绍。
文章首先介绍了多项式时间的概念,在此基础上阐述了P问题和NP问题。紧接着文章论述了理论界证明P=NP的原因,从而引出了NPC问题。在介绍了多项式归约的基础上,阐述了NPC问题的存在性,文章的最后指明,正是由于NPC的...
P-NP-NPC三者问题阐述.pdf
2010年HP实验室的P!=NP的证明(后经同行审查,证明中有错误)