首页 > 代码库 > 关于P和NP
关于P和NP
只要对算法稍有兴趣的人,总会多多少少的遇到P和NP这两个概念,而大部分书上似乎都默认大家知道这是怎么回事一样,而我恰好又不知道。
其实在我的记忆中,我已经很多次在网上查询这两个概念了,只是遗忘是可怕的……
好吧,今天想再次去搞清楚这两个概念。
在wiki上从这两个概念可以引申出很多我陌生有熟悉的概念。
多少写一些,增强一下记忆,对于在wiki上的链接就不贴了,概念太多。
这两个概念是来形容问题的,也就是说,某个问题是P的,或者NP的,即“……的问题”。
而这里是针对解决问题的算法来说的,也就是说,不管是P还是NP,都是“……的算法的问题”。
我们看到P和NP里面都有P,这个P就是多项式(polynomial)时间,说道这两个概念,应该都是“……多项式时间……的算法的问题”。补充一下,多项式时间,是一种时间测度,通常多项式时间不会随着参数的变化而发生剧烈的变化,当然高次还是很可怕的。
有了上面的理解,我们大致可以认为:
- P就是有多项式时间算法可解决的问题
- NP就有些搞了,说是有多项式时间可验证的问题
当然,上述都是在确定行图灵机上。我喜欢上面这个定义,很直观。
看,我上面说得很含糊,其实还有一个对比定义P和NP的说法:
- NP - 在非确定性图灵机上有多项式时间算法的问题
- P - 在确定性图灵机上有多项式时间算法的问题
我不太喜欢上面这个说法,是因为我还要去了解“确定性图灵机”和“非确定性图灵机”,真是个悲伤的结局……
补充一个链接 http://episte.math.ntu.edu.tw/articles/mm/mm_10_2_04/index.html
关于P和NP
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。