P问题、问题、NP问题、问题、NP完全问题和完全问题和NP难问题理解难问题理解
1.P（（polynominal）问题）问题–多项式问题多项式问题
存在多项式时间算法的问题。
2.NP（（Nondeterministic Polynominal）问题）问题–非确定多项式问题非确定多项式问题
能在多项式时间内验证得出一个正确解的问题。
关于P是否等于NP是一个存在了很久的问题，这里不做讨论。
通俗的理解这两个问题的话：在借助计算机的前提下。P问题很容易求解；NP问题不容易求解，但对于某一答案我们可以很快验证这个答
案是否正确。
3.NPH（（Nondeterminism Polynomial Hard）问题）问题–NP难问题难问题
1.它不一定是一个NP问题
2.其他属于NP的问题都可在多项式时间内归约成它。
通俗理解，NP难问题是比所有NP问题都难的问题。
4.NPC（（Nondeterminism Polynomial Complete）问题）问题–NP完全问题完全问题
1.它是一个NP问题
2.其他属于NP的问题都可在多项式时间内归约成它。
通俗理解，NP完全问题是介于NP问题和NP难问题之间的一类问题。
附上一张图，表示这些问题的关系：附上一张图，表示这些问题的关系：
作者：li1194094543
评论0