本文主要是介绍np完备性理论，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
与NP相关的总共有四类问题：P问题、NP问题、NPC问题和NP hard问题，是计算复杂度理论中研究的主要内容之一。
先介绍下多项式时间：
在计算复杂度理论中，指的是一个问题的计算时间m(n)不大于问题大小n的多项式倍数。通俗点来说，多项式时间就是指时间复杂度是个多项式，或者说,就是这个程序运行的时间随着数据规模n变化的函数为f(n)，那么,f(n)是个多项式函数,那么就可以说是控制在多项式之内。举个例子，现在从n阶图中找两点的最短路径，复杂度为n^2级别（即O(n^2)，O是大写欧），而n^2对于n是多项式（单项式当然也算），这就称为是多项式复杂度，或者多项式时间，其中问题（算法）的规模是n。如果某一个算法的规模是n，但是复杂度比如是2^n，写不成n的多项式，那就不是多项式时间。
P类问题：
所有可以在多项式时间内求解的判定问题构成P类问题。判定问题：判断是否有一种能够解决某一类问题的能行算法的研究课题。
NP类问题：
所有的非确定性多项式时间可解的判定问题构成NP类问题。非确定性算法：非确定性算法将问题分解成猜测和验证两个阶段。算法的猜测阶段是非确定性的，算法的验证阶段是确定性的，它验证猜测阶段给出解的正确性。设算法A是解一个判定问题Q的非确定性算法，如果A的验证阶段能在多项式时间内完成，则称A是一个多项式时间非确定性算法。有些计算问题是确定性的，比如加减乘除之类，你只要按照公式推导，按部就班一步步来，就可以得到结果。但是，有些问题是无法按部就班直接地计算出来。比如，找大质数的问题。有没有一个公式，你一套公式，就可以一步步推算出来，下一个质数应该是多少呢？这样的公式是没有的。再比如，大的合数分解质因数的问题，有没有一个公式，把合数代进去，就直接可以算出，它的因子各自是多少？也没有这样的公式。这种问题的答案，是无法直接计算得到的，只能通过间接的“猜算”来得到结果。这也就是非确定性问题。而这些问题的通常有个算法，它不能直接告诉你答案是什么，但可以告诉你，某个可能的结果是正确的答案还是错误的。这个可以告诉你“猜算”的答案正确与否的算法，假如可以在多项式（polynomial）时间内算出来，就叫做多项式非确定性问题。
NPC问题：
NP中的某些问题的复杂性与整个类的复杂性相关联.这些问题中任何一个如果存在多项式时间的算法,那么所有NP问题都是多项式时间可解的.这些问题被称为NP-完全问题(NPC问题)。NPC包含了NP中最难的问题。解决了这个NPC问题。所有NP 问题都能够被解决了。
NPC问题相当广泛，包括来自操作系统（调度和安全）、数据库系统、运筹学、逻辑学、特别是图论等不同领域的问题。
可满足性问题、哈密顿圈问题、巡回售货员问题、最长路径问题都是NPC问题。 装箱(bin packing)问题、背包(knapsack)问题、图的着色(graph coloring)问题以及团(clique)的问题都是著名的NPC问题。NPC问题相当广泛，包括来自操作系统（调度和安全）、数据库系统、运筹学、逻辑学、特别是图论等不同领域的问题。
NP hard问题：
Non-deterministic Polynomial hard problem(NPH)问题，如果所有NP问题可在多项式时间内转化（归约，意思是解决了后者也就相应的解决了前者）成某个问题，则该问题称为NP难问题。
这里规约的意思是将一个特殊问题一般化，即将原问题推广为一个最一般的、最有概括性、也更难的、计算复杂度更高的问题，这个问题具有最高的计算复杂度，如果这个最一般的问题也能有多项式时间求解算法，那么那些特殊的原问题也能有多项式时间求解算法。
解决了这个NP hard问题，所有NP问题都能够被解决了。
以上四个问题之间的关系如下图所示：
总结：
- P问题能够保证存在多项式时间求解算法；NP问题不确定是否存在多项式时间求解算法，但确定存在多项式时间验证算法。
- P问题是NP问题的子集，因为存在多项式时间求解算法的问题，一定能够在多项式时间内被验证。
- NP hard问题不一定是NP问题，有可能是不可判定问题。这时候说明原问题也是不可判定的。
- NPC问题既是NP问题的子集，又是NP hard问题的子集，所以NPC问题是NP问题和NP hard问题的交集。
- NP hard问题和NPC问题都要求能够在多项式时间内规约成另外一个问题。这里规约的意思是将一个特殊问题一般化，即将原问题推广为一个最一般的、最有概括性、也更难的、计算复杂度更高的问题，这个问题具有最高的计算复杂度，如果这个最一般的问题也能有多项式时间求解算法，那么那些特殊的原问题也能有多项式时间求解算法。
- 假设 N P = P 猜想不成立，那么计算复杂度的相对关系为（按照由低到高）：P <N P< N P C<N P h a r d 。
- 假设
这篇关于np完备性理论的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
