NP问题
NP问题
- NP问题 的全称是：Non deterministic Ploynomial问题，即非确定性多项式问题。
- 多项式时间（Polynomial time） 在计算复杂度理论中，指的是一个问题的计算时间m(n)不大于问题大小n的多项式倍数。
什么是非确定性问题？
有些计算问题是确定性的，比如加减乘除之类，你只要按照公式推导，按部就班一步步来，就可以得到结果。但是，有些问题是无法按部就班直接地计算出来。比如，找大质数的问题。有没有一个公式，你一套公式，就可以一步步推算出来，下一个质数应该是多少呢？这样的公式是没有的。再比如，大的合数分解质因数的问题，有没有一个公式，把合数代进去，就直接可以算出，它的因子各自是多少？也没有这样的公式。
这种问题的答案，是无法直接计算得到的，只能通过间接的“猜算”来得到结果。这也就是非确定性问题。而这些问题的通常有个算法，它不能直接告诉你答案是什么，但可以告诉你，某个可能的结果是正确的答案还是错误的。这个可以告诉你“猜算”的答案正确与否的算法，假如可以在多项式时间内算出来，就叫做多项式非确定性问题。
- NP问题 就是非确定性的多项式问题，也就是说，可以在多项式时间内验证一个解是否正确的问题是NP问题。
P问题 是能在多项式时间内求出其解的问题，所有的P问题都是NP问题，但是是否P=NP，目前还没有被证明。
（不是所有的NP问题都是难解的问题，比如数组排序的问题就是P类问题，但是P属于NP问题，所它也是NP问题，但是他并不难解。）
NP困难问题： 对于一个判定问题A,如果所有的NP问题都可以多项式时间规约到A，那么这个问题就是NP困难问题。
NPC问题： 对于一个NP问题A，如果所有的NP问题都可以多项式时间规约到A，那么这个问题就是NP困难问题。
NPC，也称NP完全问题，它是NP问题的一个子类，比如哈密尔顿回路问题就是NPC问题。它是这样描述的，给定N个顶点，以及任意两个顶点之间的距离，求出一条回路，使其经过每个顶点，且回路的总距离最短。这个问题可以通过枚举求出解，但是他的时间复杂度是(N-1)!,随着N的增大，要计算解是不可能的。
NPC有一种性质，那就是如果能证明NPC问题可以在多项式时间内求出其解，则所有的NP都可以在多项式时间内求解了，即P=NP成立。所以，我们一般认为NPC问题是难解的问题，因为他不太可能存在一个多项式时间的算法（如果存在则所有的NP问题都存在多项式时间算法，这太不可思议了，但是也不是不可能）。
NP完全问题的证明: 要证明一个判定问题是NP完全的,只要在NP完全类中找到一个问题A,将这个问题归约到待证明问题即可.要证明问题是NP完全是很困难的,因为很多问题之间的转化过程是很难想到的.第一个被证明的NP完全问题是可满足性问题,它是判定一个合取范式的布尔公式F是否存在真值指派的问题.在很多NP完全问题的证明中,我们都可以用这个问题来归约,这里不再详述。
