概念定义：
P问题：能在多项式时间内解决的问题；
NP问题：（Nondeterministic Polynomial time Problem）不能在多项式时间内解决或不确定能不能在多项式时间内解决，但能在多项式时间内验证的问题；
NPC问题：（NP Complete）NP完全问题，所有NP问题在多项式时间内都能规约（Reducibility）到它的NP问题，即解决了此NPC问题，所有NP问题也都能得到解决；
NP hard问题：NP难问题，所有NP问题在多项式时间内都能规约（Reducibility）到它的问题，但不一定是NP问题。
概念图解：
说明：
-
P问题属于NP问题，NPC问题属于NP问题；
-
NPC问题同时属于NP hard问题，是NP与NP hard问题的集合。
概念应用：
NPC问题有很多的，比较有名的有团问题，顶点覆盖集问题，支配集问题，独立集问题，哈密顿路问题，旅行商问题等，同样有很多是NP-hard而不是NPC的问题，比如围棋，停机问题等。
更多信息，请参考阅读：
http://www.matrix67.com/blog/archives/105
http://www.cnblogs.com/jpcflyer/archive/2012/04/15/2450622.html