CMP设计分享 http://blog.sciencenet.cn/u/accsys 没有逆向思维就没有科技原创。 不自信是科技创新的大敌。

博文

p与np问题的通俗解释

已有 8187 次阅读 2015-11-2 06:13 |个人分类:教学笔记|系统分类:科研笔记| NPC

       由条件和结论组成问题。解法是按照某种已知的规律(函数)从条件出发逐步将问题答案求出,这类问题是p类问题。猜测问题答案,并能够通过问题本身的条件和结论进行验证其正确与否,正确的一类条件和结论是np类问题。

      p问题的特点是不论给出什么样的条件,总可以按照规律将问题答案推导出来,具有确定性正确的特征。而np类问题的特点是未经过验证不知猜测的正确答案是否正确,具有随机性特征。这就是说,p类问题解答是一个确定性过程,而np类问题解答是一个随机性过程。

     容易理解p类问题就是np类问题,因为我们可以认为解法就是一种验证方法,把求出的答案做为猜测答案。但所有np类问题会不会都有确定的解法?如果有,则p=np,否则,p不等于np。

      直接回答p是否等于np很难。但人们研究出了所有的np类问题都可以按照某种规律转化成3元合取范式满足的3sat。3sat叫np完全问题,又叫npc。npc有很多,它们之间都可以按照确定的规律相互转化。因而,只要能够找到3sat问题解法(或其它npc问题解法)就能够确定p=np。反之,要证明存在np没有解法才行。



https://blog.sciencenet.cn/blog-340399-932675.html

上一篇:秋后算帐篇:详细解析天才的姜咏江解决了3SAT难题
下一篇:3-SAT问题为什么长期得不到解决?
收藏 IP: 111.206.20.*| 热度|

0

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2024-12-22 10:56

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部