Complexity Classes

问题的规模

问题的规模，衡量它的指标就是输入的数据在二进制编码下的长度。正因如此，背包问题才不是传统的 P 问题。

规约

规约（Reduce）是研究问题复杂性分类的一种重要工具，当我们说 $X$ 规约到 $Y$ ，即 $X{\le }_{p}Y$ ，指的是：

• 我们可以在多项式时间内，将 $X$ 问题转换成对于 $Y$ 问题的求解
• 当 $Y$ 问题输出 yes 的时候， $X$ 问题也输出 yes
• 当 $Y$ 问题输出 no 的时候， $X$ 问题也输出 no

更具体一些，reduce 又可以分为 Cook Reduce 和 Karp Reduce 两种。Cook Reduce 更加灵活，可以多次调用 $Y$ ；而 Karp Reduce 更加严苛，只能调用一次 $Y$ ，并且 $X$ 和 $Y$ 的输出必须对应。可以看出，上面的定义更偏向于 Karp Reduce 。

直观来说，$X$ 的复杂度是不低于 $Y$ 的，我们使用这个性质来定义 NPC 问题。在 NPC 问题的定义中，我们使用的是 Karp Reduce ，而 Cook Reduce 则用于解决实际问题。

P

在决策问题中，P 问题指的是，给定一个输入，存在一个算法，可以在多项式时间内给出 yes or no 的结果。

而搜索问题（也就是求解问题），可以通过二分查找的方式，规约到决策问题，所以两者本质是等价的。

需要强调，P 这个属性对应的是问题，而非具体的算法。无论多么简单的问题，我们都可以有一个指数级的复杂算法，这显然不能说明问题的难度。

NP

NP 问题（Nondeterministic Polynomial Time）指的是，在决策问题中，我们提供一个证书（certificate）和一个输入，存在一个算法（certifier）可以在多项式时间内给出 yes or no 的结果。整个证书的规模也必须小于等于输入的规模。

所谓的证书，往往就是一个“可能正确的答案”，我们的算法，也发生了从“求解”到“判别”的转变。

EXP

EXP 问题指的是，一个决策问题，给定一个输入，存在一个算法，可以在多项式时间内给出 yes or no 的结果。

严格意义上说，EXP 才更像我们理解中的那种“非常难的算法问题”，而不是 NP 。

我们有 $P\subset NP$ 。这是因为当我们给 P 提供一个“空证书”的时候，就可以将它转变成一个 NP 问题。

我们有 $NP\subset EXP$ 。这是因为我们可以遍历证书空间，给 NP 提供所有证书，进而将其转成一个 EXP 问题，而遍历是一个指数复杂度。

但是我们并不知道这三者是否相等：

NPC

NP-Complete(NPC) 是最难的一种 NP 问题，所有的 NP 问题都可以规约到 NPC 问题。

为了证明一个问题 $Y$ 是 NPC 问题，我们需要：

• 证明 $Y\in NP$
• 选择一个已知的 NPC 问题 $X$
• 证明 $X{\le }_{p}Y$

Co-NP

Co-NP 的意思是 NP 问题的补集（Complementary）。有一说一我对于这个概念理解得并不好，因为我并不知道什么是问题的补集。我只能说，NP 问题的形式往往是“是否存在一个解，可以满足某个要求”，而 Co-NP 的形式则是“是否任意解，都不满足这个要求”。

在 NP 问题中，我们可以将一个特例作为证书输入给验证器，而在 co-NP 问题中，如果仅仅输入一个反例，显然是无法满足要求的。最为朴素的做法是输入所有的可能取值，并让验证器证明这些都是反例。但是这样的时间复杂度又太高了。总之，Co-NP 也是一个非常复杂的问题。

那么 $NP=co\text{mbox}-NP$ 吗？目前没有定论，但是我们倾向于他们是不相等的。因为对于 $P$ 问题，有 $P=co\text{mbox}-P$ ，当有 $P=NP$ 时，才能有 $NP=co\text{mbox}-NP$ 。而我们知道 $P=NP$ 又不太可能。

那么 NP 问题与 co-NP 问题是完全没有交集吗？也不是，显然有 $P\subset (NP\cap co\text{mbox}-NP)$ ，但是我们不能确定是否 P 问题就等于 NP 问题与 co-NP 问题的交集，也就是 $P=(NP\cap co\text{mbox}-NP)$ 。

NP-hard

NP-hard 与 NPC 很相似，所有的 NP 问题都可以规约到 NP-hard 问题；而它与 NPC 的不同点在于，NP-hard 并不需要是一个 NP 问题。也就是说，它可能比 NPC 问题还要难。