«August 2025»
12
3456789
10111213141516
17181920212223
24252627282930
31


公告

本站技术贴除标明为“原创”的之外,其余均为网上转载,文中我会尽量保留原作者姓名,若有侵权请与我联系,我将第一时间做出修改。谢谢!

             ——既瑜


天气预报(南京)


我的分类(专题)

首页(183)
【趣味文摘】(22)
【五子连珠】(13)
【技术文档】(136)
【电脑技术】(6)
【疑难问题】(1)
【我的心情】(5)


最新日志
花语(中英文对照版)
各种花的花语
NTFS格式的7个精彩问答(pconli
童言无忌,有趣得一蹋
给MM修电脑的三个步骤[转载]
J2EE 面试题综合
JAVA编程规则
[转] P2P之UDP穿透NAT的原理与
[转]词法分析器
文件加密技术
一个让人发狂的PI求解C程序
[转]直线生成算法之DDA
[转]利用内核对象----互斥量实现应用
[转]如何正确的计算文件收发进度
双机调试VC程序
[转]分治法优化大整数乘法 C++实现
浮点数值的内存结构
[转]双链表实现大整数的加法与乘法[VC
拜占廷将军问题[转]
某人的挂QQ的程序源代码,虽然没用了,拿

最新回复
回复:vc中的CString的操作
回复:[转]分治法优化大整数乘法 C++
回复:[转]分治法优化大整数乘法 C++
回复:花语(中英文对照版)
回复:基本排序算法比较与选择[转载]
回复:c++中强制类型转换操作符小结
回复:c++中强制类型转换操作符小结
何必那么执着于是大头猫还是愤怒的小鸟,淡
回复:浮点数值的内存结构
回复:花语(中英文对照版)
回复:花语(中英文对照版)
回复:花语(中英文对照版)
回复:花语(中英文对照版)
回复:花语(中英文对照版)
回复:32位位图到24位位图的转换
dren, ages 16 and 20
回复:花语(中英文对照版)
回复:花语(中英文对照版)
回复:花语(中英文对照版)
回复:各种花的花语

留言板
签写新留言

不是0-1背包喔
桂花的花语``
谢谢
提议
提议

统计
blog名称:★既瑜★
日志总数:183
评论数量:636
留言数量:-25
访问次数:1406087
建立时间:2005年3月12日

链接


http://www.nju.edu.cn
http://bbs.nju.edu.cn 
http://www.t7-online.com
http://www.csdn.net
http://www.91f.net
http://www.crsky.com
我的MSN BLOG 

联系我

  OICQ:215768265
  njucs2001@hotmail.com
  erichoo1982@gmail.com

 

W3CHINA Blog首页    管理页面    写新日志    退出


[【技术文档】]NP问题和NPC问题(starfish)
既瑜(224499) 发表于 2005/4/15 20:10:30

什么叫做NP问题,什么叫做NPC问题? 首先说明一下问题的复杂性和算法的复杂性的区别,下面只考虑时间复杂性。算法的复杂性是指解决问题的一个具体的算法的执行时 间,这是算法的性质;问题的复杂性是指这个问题本身的复杂程度,是问题的性质。比如对于排序问题,如果我们只能通过元素间的相互比较 来确定元素间的相互位置,而没有其他的附加可用信息,则排序问题的复杂性是O(nlgn),但是排序算法有很多,冒泡法是O(n^2),快速排序平 均情况下是O(nlgn)等等,排序问题的复杂性是指在所有的解决该问题的算法中最好算法的复杂性。问题的复杂性不可能通过枚举各种可能算法 来得到,一般都是预先估计一个值,然后从理论上证明。 为了研究问题的复杂性,我们必须将问题抽象,为了简化问题,我们只考虑一类简单的问题,判定性问题,即提出一个问题,只需要 回答yes或者no的问题。任何一般的最优化问题都可以转化为一系列判定性问题,比如求图中从A到B的最短路径,可以转化成:从A到B是否有长 度为1的路径?从A到B是否有长度为2的路径?。。。从A到B是否有长度为k的路径?如果问到了k的时候回答了yes,则停止发问,我们可以说从 A到B的最短路径就是k。 如果一个判定性问题的复杂度是该问题的一个实例的规模n的多项式函数,则我们说这种可以在多项式时间内解决的判定性问题属于P 类问题。P类问题就是所有复杂度为多项式时间的问题的集合。 然而有些问题很难找到多项式时间的算法(或许根本不存在),比如找出无向图中的哈米尔顿回路问题,但是我们发现如果给了我们 该问题的一个答案,我们可以在多项式时间内判断这个答案是否正确。比如说对于哈米尔顿回路问题,给一个任意的回路,我们很容易判断他 是否是哈米尔顿回路(只要看是不是所有的顶点都在回路中就可以了)。这种可以在多项式时间内验证一个解是否正确的问题称为NP问题。显 然,所有的P类问题都是属于NP问题的,但是现在的问题是,P是否等于NP?这个问题至今还未解决。注意,NP问题不一定都是难解的问题,比如 简单的数组排序问题是P类问题,但是P属于NP,所以也是NP问题,你能说他很难解么?  刚才说了,现在还不知道是否有P=NP或者P<>NP,但是后来人们发现还有一系列的特殊NP问题,这类问题的特殊性质使得很多人相信P<>NP,只 不过现在还无法证明。这类特殊的NP问题就是NP完全问题(NPC问题,C代表complete)。NPC问题存在着一个令人惊讶的性质,即如果一个NPC 问题存在多项式时间的算法,则所有的NP问题都可以在多项式时间内求解,即P=NP成立!!这是因为,每一个NPC问题可以在多项式时间内转化 成任何一个NP问题。比如前面说的哈米尔顿回路问题就是一个NPC问题。NPC问题的历史并不久,cook在1971年找到了第一个NPC问题,此后人们 又陆续发现很多NPC问题,现在可能已经有3000多个了。所以,我们一般认为NPC问题是难解的问题,因为他不太可能存在一个多项式时间的算 法(如果存在则所有的NP问题都存在多项式时间算法,这太不可思议了,但是也不是不可能)。 类似哈米尔顿回路/路径问题,货郎担问题,集团问题,最小边覆盖问题(注意和路径覆盖的区别),等等很多问题都是NPC问题,所 以都是难解的问题。

阅读全文(3499) | 回复(0) | 编辑 | 精华


发表评论:
昵称:
密码:
主页:
标题:
验证码:  (不区分大小写,请仔细填写,输错需重写评论内容!)

站点首页 | 联系我们 | 博客注册 | 博客登陆

Sponsored By W3CHINA
W3CHINA Blog 0.8 Processed in 0.047 second(s), page refreshed 144760163 times.
《全国人大常委会关于维护互联网安全的决定》  《计算机信息网络国际联网安全保护管理办法》
苏ICP备05006046号