一、定义

• P(Polynomial, 多项式) 问题 ：可以在 多项式时间 内被 确定机 (通常意义的计算机) 解决的问题，即存在多项式时间的 算法
• NP(Non-Deterministic Polynomial, 非确定多项式) 问题 ：可以在 多项式时间 内被 非确定机 (他可以猜, 他总是能猜到最能满足你需要的那种选择) 解决的问题，即存在多项式时间的 非确定性算法
• NPC(Non-Deterministic Polynomial Complete,NP 完全) 问题 ：由其他所有 NP 问题 归约 而来的 NP 问题，它是一个 NP 问题而且所有的 NP 问题都可以归约到它
• NPH(Non-deterministic Polynomial Hard,NP 难) 问题 ，由其他所有 NP 问题 归约 而来的问题（不一定是 NP 问题），所有的 NP 问题都可以归约到它

千禧难题之首, 是说 P 问题是否等于 NP 问题, 也即是否所有在非确定机上多项式可解的问题都能在确定机上用多项式时间求解.
归约 ：将一个特殊问题一般化，即将原问题推广为一个最一般的、最有概括性、也更难的、计算复杂度更高的问题，这个问题具有最高的计算复杂度。

“问题 A 可归约为问题 B”有一个重要的直观意义：B 的时间复杂度高于或者等于 A 的时间复杂度。正如解一元二次方程比解一元一次方程难，因为解决前者的方法可以用来解决后者。

很显然，归约具有一项重要的性质：归约具有传递性。如果问题 A 可归约为问题 B，问题 B 可归约为问题 C，则问题 A 一定可归约为问题 C。

当然，我们所说的“归约”是指的 多项式 的归约 (Polynomial-time Reducible)，即变换输入的方法是能在多项式的时间里完成的。归约的过程只有用多项式的时间完成才有意义。

二、特性

• P 问题能够保证存在多项式时间求解算法；NP 问题不确定是否存在多项式时间求解算法，但确定存在多项式时间验证算法。
• P 问题是 NP 问题的子集，因为存在多项式时间求解算法的问题，一定能够在多项式时间内被验证。
• NPH 问题和 NPC 问题都是 NP 问题规约（就是说，NP-Hard 问题要比 NPC 问题的范围广）
• NPH 问题和 NPC 问题都要求能够在多项式时间内规约成另外一个问题。
• NPC 问题目前没有多项式的有效算法，只能用指数级甚至阶乘级复杂度的搜索。
• 证明一个问题是 NPC 问题的方法：先证明它至少是一个 NP 问题，再证明其中一个已知的 NPC 问题能归约到它（归约的传递性）

三、确定性和非确定性

1、确定型机器 VS 非确定型机器

• 确定型机器在每个时刻都在执行一条命令，根据这条命令，机器再去实行下一条唯一确定的命令。
• 非确定型机器对其后的步骤是有选择的，可以自由进行它想要的任意选择。如果这些后面的步骤中有一条导致问题的解，那么它总是选择这个正确的步骤。因此，非确定型机器具有非常好的猜测（优化）能力，例如应用于梯度下降。
• NP 中的每一个问题都能够用一台非确定型计算机在多项式时间内求解。
• 计算机的一个形式化模型称作图灵机 (Turing machine)。
• 但是 没有人能够构建一台非确定型计算机，非确定性是非常有用的理论结构，但是并没有人们所想的那么强大。即使使用非确定性，不可判定问题依然是不可判定的。

2、确定性问题 VS 非确定性问题

• 确定性问题：有些计算问题是确定性的，例如加减乘除，只要按照公式推导，按部就班一步步来，就可以得到结果；
• 非确定性问题：但是，有些问题是无法按部就班直接地计算出来。比如，找大质数的问题。有没有一个公式能推出下一个质数是多少呢？这种问题的答案，是无法直接计算得到的，只能通过间接的“猜算”来得到结果。而这些问题的通常有个算法，它不能直接告诉你答案是什么，但可以告诉你，某个可能的结果是正确的答案还是错误的。

3、确定性算法 VS 非确定性算法

• 确定性算法：求解过程的每一步都是确定的，例如一元二次方程的求根算法，只要传入参数，每一步求解都是确定的，这种算法就叫做确定性算法。
• 非确定性算法：非确定性算法将问题分解成猜测和验证两个阶段。算法的猜测阶段是非确定性的，算法的验证阶段是确定性的，它验证猜测阶段给出解的正确性。

我们知道，生成问题的一个解通常比验证一个猜测解要花费更多的时间。判定一个答案是可以很快利用内部知识来验证，而没有这样的提示而需要花费大量时间来求解。也就是验证很简单，求解很困难。

四、第一个 NPC 问题

NPC 问题是存在的。确实有这么一个非常具体的问题属于 NPC 问题。逻辑电路问题是第一个 NPC 问题。其它的 NPC 问题都是由这个问题归约而来的。因此，逻辑电路问题是 NPC 类问题的“鼻祖”。
逻辑电路问题是指的这样一个问题：给定一个逻辑电路，问是否存在一种输入使输出为 True。什么叫做逻辑电路呢？一个逻辑电路由若干个输入，一个输出，若干“逻辑门”组成。
逻辑电路问题属于 NPC 问题。这是有严格证明的。它显然属于 NP 问题，并且可以直接证明所有的 NP 问题都可以约化到它。证明过程相当复杂，其大概意思是说任意一个 NP 问题的输入和输出都可以转换成逻辑电路的输入和输出（想想计算机内部也不过是一些 0 和 1 的运算），因此对于一个 NP 问题来说，问题转化为了求出满足结果为 True 的一个输入（即一个可行解）。
有了第一个 NPC 问题后，一大堆 NPC 问题就出现了，因为再证明一个新的 NPC 问题只需要将一个已知的 NPC 问题归约到它就行了。后来，Hamilton 回路成了 NPC 问题，TSP 问题也成了 NPC 问题。任何一个找到了多项式算法的话所有的 NP 问题都可以完美解决了，因此说，正是因为 NPC 问题的存在，P=NP 变得难以置信。