我刚看了一下NP问题以及NP困难问题的定义，有点头晕。 用自己的话来说是这样的：
NP问题的全称是非确定性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，如果所有的NPC问题都可以用多项式时间规定为a，那么这个问题就是NPC困难问题。
NPC也成为NP完全问题，是NP问题的子类，例如汉密尔顿电路问题是NPC问题。 它描述为，给出n个顶点和任意两个顶点之间的距离，求出循环通过各顶点，并且循环的总距离最短。 这个问题可以用枚举求解，但他的时间复杂度是(N-1 )！随着n的增大，计算解是不可能的。
如果NPC能够证明NPC问题可以进一步用多项式时间求出其解，则所有NP都具有用多项式时间求解的性质。 即，P=NP为。所以，我们一般认为NPC问题是难解的问题，因为他不太可能存在一个多项式时间的算法（如果存在则所有的NP问题都存在多项式时间算法，这太不可思议了，但是也不是不可能）。
NP完全问题的证明：要证明一个判定问题是NP完全的，只要在NP完全类中找到一个问题A,将这个问题归约到待证明问题即可.要证明问题是NP完全是很困难的，因为很多问题之间的转化过程是很难想到的.第一个被证明的NP完全问题是可满足性问题，它是判定一个合取范式的布尔公式F是否存在真值指派的问题.在很多NP完全问题的证明中，我们都可以用这个问题来归约，这里不再详述.