P类问题：如果一个问题可以找到一个能在多项式的时间里解决它的算法，那么这个问题就属于P问题。
NP问题：是指可以在多项式的时间里验证一个解的问题。NP问题的另一个定义是，可以在多项式的时间里猜出一个解的问题。
之所以要定义NP问题，是因为通常只有NP问题才可能找到多项式的算法。
约化(Reducibility，有的资料上叫“归约”)：一个问题A可以约化为问题B的含义即是，可以用问题B的解法解决问题A，或者说，问题A可以“变成”问题B。 “问题A可约化为问题B”有一个重要的直观意义：B的时间复杂度高于或者等于A的时间复杂度。而且，约化具有传递性。
NPC(NP-完全问题)：
1、是一个NP问题
2、所有的NP问题都可以约化到它
NP-Hard问题：它满足NPC问题定义的第二条但不一定要满足第一条（就是说，NP-Hard问题要比 NPC问题的范围广）。NP-Hard问题同样难以找到多项式的算法，但它不列入我们的研究范围，因为它不一定是NP问题。
这几者的关系我大致画了个图来说明。 简单总结：P和NP问题可以找到多项式解法，而NPC和NPC-Hard则很难找到。这个文章其实要弄明白的一个点就是，我们平时所说的"这个问题是NP问题，只能用暴力搜索来解"， 其实正确的说法是NPC问题。
网友评论