我有一个一直误解的地方，打个比方，时间复杂度来判定当前的算法和输入输出。这听起来很有道理没问题，但是时间复杂度并不是来判断这个的。时间复杂度判断的是当输入规模巨大变到数百倍或者数万倍时等等，程序运行时间的变化情况与复杂程度。如哈希，不管数据多大，找到总是一次性找到，那么这时候时间复杂度就是O(1)。如找到数组中最大的元素，不管数组规模有多大，n个数中找到最大的总是O(n)。以此类推还有O(na), O(log n)等等。注意，没有O(n2 + n3)，这个2这时候不是影响程序增长的主要因素，指数3才是。所以这时候时间复杂度还是O(n3)。还有前面的系数O(2n2)，在数据增长的时候其实和算法变化和系数无关，这里也不写他，其实就是O(n2)。比如还有一个问题，有个数学家说过，因为指数函数增长的爆炸性。最大的幂函数也不能和哪怕是很小的指示函数相提并论（比如O(n10000)和O(1.0001n)）。因为总有一个阈值，指示函数的增长速度会大于幂函数。这个可以自己求导试试，虽然那个数有可能巨大，但是总是存在的。所以，我们给出概念：多项式级复杂度：O(na)，O(log n) ，O(1)等等。非多项式级复杂度：O(an)和O(n!)等。
《算法导论》中有一个例子：现在有两个问题：求解一个一元一次方程和求解一个一元二次方程。那么我们说，前者可以规约为后者，意即知道如何解一个一元二次方程那么一定能解出一元一次方程。我们可以写出两个程序分别对应两个问题，那么我们能找到一个“规则”，按照这个规则把解一元一次方程程序的输入数据变一下，用在解一元二次方程的程序上，两个程序总能得到一样的结果。这个规则即是：两个方程的对应项系数不变，一元二次方程的二次项系数为0。从规约的定义中我们看到，一个问题规约为另一个问题，时间复杂度增加了，问题的应用范围也增大了。
P类问题：Polynominal，存在多项式时间算法的问题。NP类问题：Nondeterministic polynominal，非确定性多项式问题。他没有确定的多项式算法去解（求不出来，不知道他的解法到底是不是多项式）。但是可以用多项式算法去验证的问题。所以可以得到，P类问题其实就是有确定性多项式算法的NP类问题，P类问题是NP类问题的子集。给一个很有名的NP类问题理解一下：旅行家推销问题(TSP)。即有一个推销员，要到n个城市推销商品，他要找出一个包含所有n个城市的环路，这个环路路径小于a。我们知道这个问题如果单纯的用枚举法来列举的话会有(n-1)! 种，已经不是多项式时间的算法了，(注：阶乘算法比多项式的复杂)。那怎么办呢？我们可以用猜的，假设我人品好，猜几次就猜中了一条小于长度a的路径，我画画画画，好的，我得到了一条路径小于a的环路，问题解决了，皆大欢喜。可是，我不可能每次都猜的那么准，也许我要猜完所有种呢？所以我们说，这是一个NP类问题。也就是，我们能在多项式的时间内验证并得出问题的正确解，可是我们却不知道该问题是否存在一个多项式时间的算法，每次都能解决他(注意，这里是不知道，不是不存在)。
由上面讲述可知，P=NP这个千年问题就得知道是什么了。是不是每个NP类问题都可以有个P类算法去解呢（NP类可以用P类多项式验证）？
规约我们知道，一元一次到一元二次是规约。因为知道了一元二次，一元一次必有解（一元一次其实就是某种形式的一元二次）。所以NPC就是所有NP问题规约成的东西。解决了他，所有NP问题都解决了。满足两个条件。第一个，它是一个NP问题。第二个，所有的NP问题都能规约到他。
NP-Hard问题是这样一种问题，它满足NPC问题定义的第二条但不一定要满足第一条（就是说，NP-Hard问题要比 NPC问题的范围广，NP-Hard问题没有限定属于NP），即所有的NP问题都能约化到它，但是他不一定是一个NP问题。NP-Hard问题同样难以找到多项式的算法，但它不列入我们的研究范围，因为它不一定是NP问题。即使NPC问题发现了多项式级的算法，NP-Hard问题有可能仍然无法得到多项式级的算法。事实上，由于NP-Hard放宽了限定条件，它将有可能比所有的NPC问题的时间复杂度更高从而更难以解决。（太复杂不做要求）