注意NP、P、NPC、NP-hard 概念大部分参考知乎：https://zhuanlan.zhihu.com/p/235301347.

图灵机¹

图灵机是一个模拟算法运行的抽象机器，定义如下：

1. 有一个无限长度的磁带，这个磁带被分成了一个接一个的单元格，磁带被用于写入字母和符号。
2. 一个读写磁带的磁头，这个磁头负责控制堆磁带的写入和左右移动。
3. 一个状态寄存器，用来存储图灵机的状态。
4. 一个指令表，可以根据机器当前所处的状态和磁带上当前的符号，指示机器进行特定的操作。比如：擦除或者写入一个符号、向左或者向右移动磁头。

确定图灵机和非确定图灵机

在确定性图灵机（DTM）中，其控制规则规定了在任何给定情况下最多只能执行一个动作。在理论计算机科学中，非确定性图灵机（NTM）是一种理论计算模型，其控制规则在某些给定情况下指定了多个可能的动作。 也就是说，NTM的下一个状态不是完全由其动作和它所看到的当前符号决定的（不同于确定性图灵机）。

Note：任何NDTM可以转换为DTM(反之亦然)，即二者虽然运行时不同，但最终结果等价。

NP问题

定义

非确定型图灵机在多项式时间内可以找到解的问题，简单说就是可以在多项式时间里验证一个解的问题。

延伸

P问题属于NP问题，但P问题是否等于NP问题，目前仍然是一个世界难题。

P问题

定义

确定型图灵机在多项式时间内可以解决的问题，简单说就是可以在多项式时间里解决的问题。

延伸

一般来说，P问题在生活中更有意义。因为可以在多项式时间里解决就意味着问题复杂度不会随着数据规模的扩大而指数爆炸，在生活中更容易被解决。

约化(Reducibility)

定义

A问题可以约化成B问题，代表可以用B问题的解法解决A问题。如“求解一元一次方程” 问题可以约化成 “求解一元二次方程” 问题，只需要令 “求解一元二次方程” 问题中二次项系数为 即可解决 “求解一元一次方程” 问题。

延伸

约化的过程是难度升级的过程，且约化具有传递性。

NP-complete 问题(NPC)

定义

NPC问题即为所有NP问题可以约化到的一个问题，是所有NP问题中最复杂的问题。NPC问题满足条件：

1. 该问题是一个NP问题；
2. 该问题可以由一个已知的NPC问题约化到它。

第一个NPC问题是逻辑电路问题。

NP-hard 问题

定义

NP-hard 问题即满足NPC问题的第二个条件，但不一定满足第一个条件，因此NP-hard要比NPC问题范围更广，NP-hard问题不一定是NP问题。