哎呀，博士补习闪回。好的，去。

我们从决策问题的概念开始，决策问题是算法始终可以回答“是”或“否”的问题。我们还需要两种计算机模型（实际上是图灵机）的想法：确定性模型和非确定性模型。确定性计算机是我们一直在思考的常规计算机。一台不确定的计算机就像我们习惯的那样，除了具有无限的并行性之外，因此，每当您进入分支机构时，都将产生一个新的“进程”并检查双方。就像瑜伽士贝拉（Yogi
Berra）所说的那样，当您在路上遇到叉子时，应该抓住它。

如果存在已知的多项式时间算法来获得该答案，则决策问题在P中。如果存在用于非确定性机器的已知多项式时间算法来获得答案，则决策问题就在NP中。

在P中已知的问题在NP中微不足道-
非确定性机器永远不会麻烦自己派生另一个进程，其行为就像确定性过程一样。已知在P和NP中都不存在问题。一个简单的例子是枚举长度为n的所有位向量。无论如何，这需要2
n个步骤。

（严格来说，如果节点确定性机器可以在多重时间内得出答案，而确定性机器可以在多重时间内 验证 解是否正确，则决策问题就在NP中。）

但是，在NP中存在一些已知的问题，对于这些问题，还没有多时确定算法。换句话说，我们知道他们在NP中，但是不知道他们是否在P中。传统示例是“旅行推销员问题”的决策问题版本（decision-
TSP）：给定城市和距离，是否有一条路线覆盖所有城市，并且返回起点小于 x
距离？在不确定性机器上这很容易，因为每次不确定性旅行推销员每次上路时，他都会抓住它：他的克隆人前往他们没去过的下一个城市，最后，他们比较注释并查看是否任何克隆都花费不到
x的 距离。

（然后，成倍地增加了许多克隆，以应对必须杀死的克隆。）

尚不知道决策TSP是否包含在P中：没有已知的多时解决方案，但是没有证据表明这种解决方案不存在。

现在，再提出一个概念：给定决策问题P和Q，如果算法可以将P的解转换为多项式时间内的Q的解，则可以说Q是对P的多项式 可约的 （或仅可约的）。

如果您可以证明（1）它在NP中，并且（2）表明它可以在多项时间上归结为一个已知为NP完全的问题，那么该问题就是NP完全的。（其中最困难的部分是证明NP完全问题的
第一个 例子：这是由Steve
Cook在Cook的定理中完成的。）

所以说的真的是，如果有人找到一个NP完全问题的多时制解决方案，那么他们会自动为 所有 NP完全问题找到一个解决方案。这也意味着P = NP。

当且仅当与“ NP完全问题”一样“至少”困难时，问题才是NP困难的问题。寻找最短路线的更常规的旅行推销员问题是NP难的，而不是严格的NP完全的。