1.概念
P问题就是指该问题能在多项式复杂度内解决。
NP问题就是指该问题能在多项式复杂度内被验证。
复杂度一般用大写字母O表示，多项式复杂度记为O(n(^k))。
NP-hard问题就是比NP问题更困难解决的问题，通常NP问题都可以说是NP-hard问题，但是不是所有的NP-hard问题都是NP问题（能否被验证？）
NP-complete（NPC问题）就是既是NP问题也是NP-hard问题。
2.常见问题复杂度表（Wikipedia）
3.证明
（1）证明NP问题。这个容易，即给你一个结果，你能在polynomial的时间内验证该结果的正确性。
（2）证明NP-hard问题。我们要证明一个问题是NP-hard的时候，我们通常要做的是找到一个已被证明了的NPC问题，并把这个NPC问题归约到该问题上去（即NPC<=NP-hard）。
证明NP-hard问题是比较常用的一个，去规约到一个NPC问题（在NPC列表里面找到可以规约的）
https://en.wikipedia.org/wiki/List_of_NP-complete_problems
（3）证明NP-Complete问题。分以下两步：
3.1 第一步证明这个问题属于NP；
3.2 第二步，证明这个问题是NP-hard的。
网友评论