P,NP,NPC

什么是P问题，P问题是确定性图灵机在多项式时间内可解的问题
NP问题是确定性图灵机不能在多项式时间内解决或不确定能不能在多项式时间内解决，但可以在多项式时间内验证或者非确定性图灵机可以在多项式时间内解决的问题
那么多项式时间是什么？
用易于程序员理解的方式表达，多项式时间描述的是这样一种算法，它的时间复杂度不以指数形式增长，那么在有限的时间内就可以得到结果（这个描述并不正确，感兴趣可以更深入了解这一点，只是想了解的话有这样的理解就可以了）
例如：复杂度为O(2^k)的算法，是不能在多项式时间内解出的算法
复杂度为O(k^1000)的算法，是能在多项式时间内解出的算法
（这只是理论上的定义，实际使用上n^2都已经算不出来了(夸张)，要看具体的数据量再做选择）

什么是NPC？
NPC是NP完全问题，是所有的NP问题都可以约化到的问题，是最难的NP问题
什么是约化？
约化就是把问题A转化成问题B，从而用问题B的算法解决问题A，显然问题B要比问题A复杂。
如果把最难的NPC问题解决了，那么所有的NP问题也就解决了