P、NP、NPC（NP完全问题）、NP-hard问题概述
一、概念总结1.P问题: 能在多项式时间内解决的问题
2.NP问题: 不能在多项式时间内解决或不确定能不能在多项式时间内解决，但能在多项式时间验证的问题
3.NPC: NP完全问题，所有NP问题在多项式时间内都能约化(Reducibility)到它的NP问题，即解决了此NPC问题，所有NP问题也都得到解决。
4.NP hard:NP难问题，所有NP问题在多项式时间内都能约化(Reducibility)到它的问题(不一定是NP问题)。
二、四者联系的图形表示
最近在做压缩感知的相关研究，一直对P、NP等问题一知半解，知道看到了这几篇博文才算真正了解了这几大问题的差异。
博文地址如下：
第一篇详细做了这些问题的总结与讲解，第二篇是一个简短的概述。
/jbb0523/article/details/40710449
/jpcflyer/archive//04/15/2450622.html）
本篇博文主要为了自己在想到时再回顾这些概念做了个梳理总结
一、概念总结
1.P问题: 能在多项式时间内解决的问题
一般而言，多项式时间可解意味着时间复杂度为O(1)、O(n)、O(logn)
时间复杂度并不是表示一个程序解决问题需要花多少时间，而是当问题规模扩大后，程序需要的时间长度增长得有多快。
2.NP问题: 不能在多项式时间内解决或不确定能不能在多项式时间内解决，但能在多项式时间验证的问题
3.NPC: NP完全问题，所有NP问题在多项式时间内都能约化(Reducibility)到它的NP问题，即解决了此NPC问题，所有NP问题也都得到解决。
NPC问题包含2部分：1.它是个NP问题、2.所有的问题都可以约化到它
补充：约化的概念
一个问题A可以约化为问题B的含义即是，可以用问题B的解法解决问题A
从时间复杂度来讲，就是B问题的时间复杂度大于或等于A问题的时间复杂度，可以用求解B问题的算法来求解A问题。
4.NP hard:NP难问题，所有NP问题在多项式时间内都能约化(Reducibility)到它的问题(不一定是NP问题)。
NP-hard问题满足NPC问题的第二个条件但不满足第一个条件。
二、四者联系的图形表示
P问题属于NP问题，NPC问题属于NP问题。
NPC问题同时属于NP hard问题，是NP与NPhard的交集。
