共计 1719 个字符，预计需要花费 5 分钟才能阅读完成。
本博客参考：
- https://zhuanlan.zhihu.com/p/348250098
- https://zhuanlan.zhihu.com/p/348020672
- https://zhuanlan.zhihu.com/p/260512272
- 以及相干的 1 -6。
是什么
NP 的全称是 Non Deteministic Polynomial，是线性所不能判断的问题的汇合。
NP 这个货色是从哪里来的呢？
起源
NP 的提出，是基于图灵机模型的。
什么是图灵机？
图灵机有 k 条带子，左端无限，右端要多长能够有多长（潜在有限长）。每条带子都按程序划分了格子，一个格子能够记录一个符号。符号的无限集咱们称之为字母表（alphabet）. 每条带子上有一个带头（tape head），能够读取或更改一个格子里的内容。带头能够左右挪动，咱们规定图灵机的每个步骤中，带头只能向左一格、向右一格或不动。
用最艰深的语言来解释，图灵机是运行在 3 条带子和寄存器上的合乎规定的自动化的机器。
用图灵机解决问题
有了这个机器，怎么才算应用这个机器解决了问题呢？为了简洁，咱们目前只限定“判断命题是否为真”这种判断类问题。
当对输出和问题，图灵机运算后，图灵机能停，并且输入断定后果，则称图灵机解决了此问题。
艰深了解，是对于一个命题，图灵机可能不死循环，并且输入判断后果是真是否，那么就说此问题被图灵机解决。
对图灵机的大胆猜想
强邱奇 - 图灵（CT）论题：任何物理上可实现的计算安装 A，都可被图灵机以多项式代价模仿。
再换句话说，任何安装都能够别图灵机以多项式的代价模仿。
不过请留神，这是一个 论题 ，不是论断，是一个猜测。
为了验证此猜测，其举例了三个安装，每一个安装都能用图灵机“代替”，三个安装别离是：1. 任意大的字母表；2. 单带图灵机；3. 双向图灵机。（感兴趣能够看原帖子，咱们只须要了解，此猜测大胆认为任何安装都能被以线性代价图灵机模仿代替。）
图灵机的泛化
该泛化认为，任意一个安装 / 程序，都能够被看成一个“通用图灵机”，即输出 - 解决 - 输入。
以以后咱们相熟的货色举个例子，对于某一个独自的指令，一个主机能够被看成图灵机；一个手机能够被看成图灵机；以及 一个程序，也能够被看成一个图灵机。
对图灵机解决问题的复杂度
A reminder，“解决问题”的定义，是图灵机可能判断此命题是否为真。
联合 C - T 论题，咱们把所有具备多项式工夫算法的问题认为是同一类，也就是 P (Polynomial)类。凡是在这类外面的问题，都被叫做在图灵机上有“高效算法”。
这其实也变相申明了图灵机的计算复杂度下限，是线性问题，也就是复杂度 $O(1)、O(n^a)、O(log_a(n))$，其中 $a$ 是常数。
非确定性图灵机
刚刚咱们所“相熟”的图灵机，叫做确定性图灵机。还有一种，叫做非确定性图灵机。二者比照：
换一张：
能够看到，左侧的状况下，对于计算的“搜寻”的效率，不如右侧的高。
这种非确定性的图灵机，通常用来解决存在性问题。NDTM 的每一条计算门路试图结构一个存在性证实，若结构胜利，在输入带上写 1 并停机，称该计算是胜利的，该终止格局为承受格局；若结构失败，在输入带上写 0 并停机，称该计算是失败的，该终止格局为回绝格局；永不终止的计算门路也视为失败的。
看到这里，目前所有的程序，都是左侧的图灵机的泛化，对于右侧的非确定性图灵机，还没有一个物理事实（不过如同量子计算机就是，然而还没实用）。在原帖中，对于非线性复杂度的问题，右侧的非确定性图灵机可能以线性复杂度解决。
所以呈现了 P 类问题 Polynomial，即能应用确定性图灵机有高效解决办法的问题；和 NP 问题 Non deterministic Polynomial，不能用确定性图灵机线性判断的问题。
回到当初，网络上的帖子
看到很多视频或者答复说 P 问题就 O()多少的问题，而后复杂度上到 O 多少，就是 NP 问题了。
的确说的也不能算错，就是这个 NP 呈现的源头，其实算是说，有没有存在一个“高效算法”在以后这个问题上。
因为当初所有的程序都是确定性图灵机的泛化，所以对于非线性的复杂度问题是不存在“高效算法”的。当初大家也不说 deterministic 了，只说是否在正当工夫下输入后果。这也算概念的引申吧！
