Question

什么是np?

Answer 1

由条件和结论组成问题。解法是按照某种已知的规律（函数）从条件出发逐步将问题答案求出，这类问题是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没有解法才行。