Intractability: P, NP, NPC

概念

多项式时间规约 Polynomial-time Reduction

如果一个问题 $X$ 可以多项式规约到问题 $Y$,如果任意问题 $X$ 的输入能够通过如下步骤的组合得到:

  • 多项式次数的计算
  • 多项式次数查询问题 $Y$ 的真实结果

那么就认为 $X$ 可以多项式规约到问题 $Y$,记做 $X \leq_{p} Y$。 相当于 $X \leq_{p} Y ~ \mathrm{iff} ~ x\in X \Leftrightarrow f(x) \in Y$.

直观的理解这样一条概念:对于问题 $X$ 的任何输入,我们都可以问题 $Y$ 的算法和多项式级别的操作就解决,那么问题 $X$ 肯定不会难于问题 $Y$。

那么证明这种规约关系的时候,只需要构造出这样一个算法转换的过程,利用问题 $Y$ 解决问题 $X$,即可得证。

P、NP、NPC

P 问题

P 问题是多项式时间内可以求解的判定性问题所构成的集合。假定问题 $X$ 是 P 问题,那么我们可以得到如下抽象:

  • 问题 $X$ 一个集合的字符串组成
  • 问题 $X$ 的一个输入 $x$ 是一个字符串
  • 问题 $X$ 的算法 $A$ 要能在多项式的时间复杂度内做到:$A(x) =\begin{cases} yes, x\in X\\ no, x \notin X.\end{cases}$

传统多项式算法解决的问题都可以转化为这样的一个判定性问题,例如:最短路问题,我们可以将它拆成和问题规模一致的判定性问题进行解答:最短路是否小于等于 1、最短路是否小于等于 2、最短路是否小于等于 3……

因此, P 问题也有一个很通俗的解释:在多项式时间复杂度内能够求得一个答案的问题,俗称算得快。

NP 问题

NP 问题(全称 Non-deterministic Polynomial Problem)存在多项式时间内运行完毕的验证器的判定性问题的集合。假定问题 $X$ 是 NP 问题,我们可以得到如下抽象:

  • 问题 $X$ 一个集合的字符串组成
  • 输入为问题 $X$ 中的一个字符串 $s$
  • 存在一个针对 $s$ 的 $t$ 与一个多项式时间复杂度的验证器 $C(s, t) = yes$

其实重点在于非确定性,通俗来讲就是,对于一个判定性问题,虽然我们没有办法在多项式时间复杂度内回答它,但是我以非常好的运气随机画了一组满足判定的解答,我需要能够在多项式时间复杂度内验证它能够满足判定。

因此,NP 问题也有一个很通俗的解释:在多项式时间复杂度内能够验证一个解答是否正确,俗称验得快。

证明一个问题是 NP 问题,通常只需要给出两样东西的定义即可(Certificate、Certifier),Certificate 是这个问题一组解答的定义,Certifier 是多项式时间复杂度内验证问题解答是否正确的方法。

NP-Complete 问题

这是一类特殊的 NP 问题的集合,问题 $X$ 是 NP-Complete 问题当且仅当问题 $X$ 是 NP 问题且任何 NP 问题 $Y$ 都可以多项式规约到问题 $X$。

说它特殊是因为按照 NPC 问题的定义,一旦任何一个 NPC 问题被证明是 P 问题,那么世界上所有的 NP 问题都是 P 问题了,即 P = NP。

按照定义,证明一个问题 $X$ 是 NP-Complete 问题,需要以下步骤:

  • 证明问题 $X$ 是 NP 问题
  • 选择一个 NPC 问题 $Y$
  • 证明 $X \leq_{p} Y$

Quiz

选择了一些我想了一些时间,觉得还是比较有意思的题目进行分享。

为了证明 Partition 能够多项式规约到 Bin Packing,我们需要找到利用 Bin Packing 的算法解决 Partition 问题。

首先我们将集合 $S$ 中的 0 全部扔掉,因为 0 在划分的时候属于任意集合都可以不影响判定问题的结果。接着,我们将剩余的元素中的负数转化为其相反数,一个负数加入集合 $S1$ 相当于其相反数加入集合 $S2$,也不影响判定性问题的结果。

将现在得到的数字集合记为 $S’$ 且满足每一个数字都是正数,我们将其放进 Bin Packing 问题中,尝试将集合 $S’$ 塞进两个桶中,且每个桶容量上限都是所有数字和的一半。如果 Bin Packing 返回 Yes,那么对应的方案就可以作为 Partition 问题的方案返回,所以 Partition 也应该输出 Yes。如果 Partition 存在可行方案,那么按照我们的构造 Bin Packing 也应该存在可行方案,$P \Rightarrow BP$ 成立,逆否命题 $\lnot BP \Rightarrow \lnot P$ 成立,故如果 Bin Packing 返回 No,Partition 的结果也应该是 No。

如此,我们完成了利用 Bin Packing 的算法解决 Partition 问题,故多项式时间规约得证。

问题中我们要证明 D2IS 是 NPC,首先要证明 D2IS 是 NP 问题,这一步是很简单的,故略过。

接着,我们要将一个 NPC 问题多项式规约到 D2IS 问题,这里我们使用 IS 问题(最大独立集问题)。

IS 问题与 D2IS 问题最大的区别是 IS 要求 $V’$ 中的点之间的距离大于等于 2,而 D2IS 要求正好等于 2。我们只需要解决这一个问题就能轻松地在这两个问题之间互相转化。对于 IS 中的图 $G=(V, E)$,我们加入一个新的点 $x$,使其和原图中的所有点都连一条边,转化为新图 $G’ = \left (E\cup \{x\}, V\cup \left (\bigcup\limits_{v \in V}(x, v)\right )\right)$。

如此,新加入的点将原图中任意两个点的距离都拉进到了至多 2,成功解决了 IS 允许距离大于等于 2 的问题。同时新加入的点不会影响 IS 问题的判定,因为一旦选择新加入的点到 IS 那么最大独立集大小为 1,等价于在原图中随便选择一个点的方案。

上一篇