|||
由条件和结论组成问题。解法是按照某种已知的规律(函数)从条件出发逐步将问题答案求出,这类问题是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没有解法才行。
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-12-22 10:56
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社