关于算法中的NP问题

在讲P类问题之前先介绍个概念：时间复杂度。

时间复杂度：

时间复杂度并不是表示一个程序解决问题需要花多少时间，而是当问题规模扩大后，程序需要的时间长度增长得有多快。也就是说，对于高速处理数据的计算机来说，处理某一个特定数据的效率不能衡量一个程序的好坏，而应该看当这个数据的规模变大到数百倍后，程序运行时间是否还是一样，或者也跟着慢了数百倍，或者变慢了数万倍。不管数据有多大，程序处理花的时间始终是那么多的，我们就说这个程序很好。

P类问题

• 存在多项式时间算法的问题。(P：polynominal，多项式)

NP类问题

• 能在多项式时间内验证得出一个正确解的问题。(NP:Nondeterministic polynominal，非确定性多项式)
• P类问题是NP问题的子集，因为存在多项式时间解法的问题，总能在多项式时间内验证他。

NPC问题

• 如果所有np问题都能在多项式时间内转化为他，则称该np问题为npc问题(NPC:NP complete又叫NP完全问题)
• NPC问题是NP问题的子集。

NPH问题

• 又叫NP难问题，他不是一个NP问题，然后所有的NPC问题都可以在多项式时间内转化为他的话，就叫他NPH（hard）问题。