P、NP、NPC、NP-hard问题

其中有一部分引用此博客http://blog.sciencenet.cn/blog-327757-531546.html

要计算或解决一个问题，该问题通常有一个大小规模，用n表示。例如，若分析计算一个二进制数，该数有多少位，这个位就是其大小规模。再比如，从n个数里面找出最大的那个数，这个n就是该问题的规模大小。怎么找？我们要比较n-1次才能得到结果，这个n-1就是所花的时间，也就是时间复杂度。再比如，将n个数按从大至小排序，n是其规模大小，若是我们按这样的方法：第一次从n个数里找最大，第二次从n-1个数里找最大，以此类推，需要的比较次数就是n(n-1)/2,称我们所用的方法为算法，称n(n-1)/2为该算法的时间复杂度。对于时间复杂度，当n足够大时，我们只注重最高次方的那一项，其他各项可以忽略，另外，其常数系数也不重要，所以，n(n-1)/2我们只重视n的平方这一项了，记为O(n的平方），这就是该算法对该问题的时间复杂度的专业表示。

所有形如a*n^k+b*n^(k-1)+c*n^(k-2)……都可记为O(n^k), n^k表示n的k次方，为乘号，这样的复杂度称为多项式时间复杂度，若是时间复杂度形如k^n，k为大于1的常数，或n!，或更大的，就称为指数型时间复杂度。显然，当n足够大时，指数型时间比多项式要大得多的多。

p问题：能够在多项式时间内解决的问题

NP问题：能够在多项式时间内验证的问题，P问题与NP问题考虑维度不同，p问题从解决上来考虑问题，而NP问题只是你给出一个解决方案，是否能够在多项式时间内验证

注：约化/规约（Reducibility）：一个问题A可以约化为问题B的含义即是，可以用问题B的解法解决问题A

NPC问题：1是一个NP问题2NP问题都可以约化到它

NP-hard问题：满足2不一定满足1