P问题：指的是能在多项式时间内解决的问题。
NP问题：指的是能在多项式时间内验证的问题。在此，我们可以看出所有的P问题都属于NP问题，但是P是否等于NP呢，至今还未得到验证，即既证明不了P=NP，也证明不了P≠NP。
NPC问题（NP完全问题）：是指NP问题中最难的一类问题。证明一个问题是否是NPC问题：（1）先证明此问题是NP问题；（2）此问题可以通过一个已知是NPC的问题规约得到。由证明可知，必须得先定义第一个NPC问题，即电路可满足性问题。
NP-hard问题：这类问题至少比NP问题难。
————————————————
版权声明：本文为CSDN博主「Louis_lan」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/liu14lang/article/details/84898516
=====
NP-hard：比所有的NP问题都难的问题
怎么理解 P 问题和 NP 问题？ - 王宇的回答 - 知乎
https://www.zhihu.com/question/27039635/answer/101730260
=======
NP问题有很多种，但若所有的NP问题都能多项式归约到问题X，X为NP hard
这里又要说道归约上了。如果A能用多项式次的B解决，称A能多项式归约到B。比如说现在问题A为判定二年级是否有人刷知乎, 那我可以把这个问题规约到问题B:判定每个班级是否有人刷知乎。 只要对二年级所有的班级做一边问题B，就能得到A的结果，如果这个次数是输入规模的多项式级别，我们认为A可以多项式规约到B。
作者：武翔宇
链接：https://www.zhihu.com/question/27039635/answer/49977321
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
=====
例子：k-clique问题：
problem： Prove that the following problem is NP-complete:given an undirected graph G=(V,E) and an integer k,
return a clique of size k as well as an independent set of size k,provided both exist.
首先，独立集和团是两个相对的概念，找K个元素的独立集和团是可以等价的。
对于任意一个有k个项的3SAT表达式，我们对于每个项构造一个三点三边呈现三角形的子图，（共有k个三角形）
对于每个变量，两种相反的形式（每隔变量取非）之间连一条边，如果能够找到k个元素的独立集，必然k个点分布在k个三角形，即选择了k个变量，使得表达式满足。
于是，当我们有多项式时间算法解决k独立集问题时，我们就一定有多项式时间算法解决3SAT问题，所以k独立集问题是NP-complete problem.
同样的，k独立集的等价命题 k-clique问题也是NP-complete的。
————————————————
版权声明：本文为CSDN博主「cryqqqcy」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/cryqqqcy/article/details/75118779