计算复杂性入门：P、NP、NP完全与困难问题求解

前面几篇分别求出了最优调度、讨论了匹配与独立集。接下来把视角从“某个算法要做多少工作”，转向“一个问题是否存在高效算法”。

本文区分求解、验证与归约，建立P、NP、NP-hard、NP-complete的关系，并讨论困难问题的求解方法。需要了解输入编码与复杂度和图上的独立集。

上一篇：图上的组合优化。专题入口：算法设计与分析导论。

1. 为什么先研究判定问题

判定问题对每个输入回答是或否，便于精确定义哪些输入属于问题的“是实例”。判定、最优值与最优方案的区别，见导论。

以独立集为例：输入图G与整数k，问是否存在至少k个两两不相邻的顶点。求最大独立集则要求最大数量或具体集合。得到最优方案通常能够计算最优值并回答阈值判定，但仅知道一个阈值的答案，不会自动给出最优方案。

2. 多项式时间、P与NP

这里的输入规模L是编码长度。多项式时间要求存在固定常数，使运行时间被L的固定次幂上界控制。指数中的次数不能随输入参数增加而无限改变；巨大次数或常数也可能让多项式算法在实践中不适用。

2.1 P：能够在多项式时间求解

P是确定性多项式时间可判定的问题类。给定合法编码，算法必须在多项式时间内给出是或否。

2.2 NP：正实例具有可快速验证的证书

NP是nondeterministic polynomial time，即非确定性多项式时间。等价的验证刻画是：对每个答案为“是”的输入，存在长度至多为输入长度多项式的证书，确定性验证器能在多项式时间确认它；答案为“否”的输入，不存在能被该验证器接受的证书。

独立集判定的证书是一组顶点编号。检查编号合法、数量至少k、任意冲突边未被同时选入，即可接受。集合的合法性检查代码在图优化篇。

这里验证的是“存在达到k的可行解”，而不是“这份集合已经全局最大”。定义参见Stephen Cook的问题说明。

3. NP-hard与NP-complete

先采用判定问题之间的多项式时间多对一归约，记作 $A\le_p B$；下一节给出转换的含义。

B是NP-hard：每个NP问题都可在多项式时间归约到B。
B是NP-complete：B既是NP-hard，又属于NP。

类别	需要属于NP吗	核心要求
P	是，P包含于NP	多项式时间求解
NP	按定义是	正实例有多项式长度证书与验证器
NP-hard	不要求	至少能承接所有NP问题的求解
NP-complete	要求	NP成员性加NP-hard性

所以证明NP完全需要“能验证”与“足够难”两部分。NP-hard本身不提供证书验证的保证，甚至不要求该判定问题可判定。

优化任务也常称NP-hard：例如若能在多项式时间求最大独立集的最优值，就能与k比较，解决其NP完全判定版。这是在求解任务意义下说困难性；NP-complete通常用于判定版本。相关证明可参看Michael Dinitz的NP完全性讲义。

4. 多项式归约：用B的求解器回答A

$$ A\le_p B \iff \exists\text{多项式时间可计算的 }f,\ x\in A\Longleftrightarrow f(x)\in B $$

含义是把A的实例x转换成B的实例f(x)，保留是/否答案。然后调用B的求解器，将结果作为A的答案。

A的输入经过多项式转换成为B实例，再调用B求解器得到A答案

若B能多项式求解，转换加求解仍为多项式，于是A也能多项式求解。要用已知难问题A证明B很难，应构造A→B，而不是只把B变成A。

4.1 完整小例子：团到独立集

团是一组两两相邻的顶点。给无向简单图G构造补图：顶点相同，两个不同顶点在补图中连边，当且仅当它们在G中没有边。

因此同一个顶点集合S满足：

$$ S\text{是G的团}\Longleftrightarrow S\text{是补图}\ \overline G\ \text{的独立集} $$

阈值k保持不变。团判定(G,k)转换为独立集判定(补图G,k)，答案双向一致，转换只需检查每对顶点。这是团到独立集归约的基本结构。

4.2 Python实现转换

from itertools import combinations


def clique_to_independent(vertices, edges, k):
    vertices = list(vertices)
    edge_set = {frozenset((u, v)) for u, v in edges}
    complement = [
        (u, v) for u, v in combinations(vertices, 2)
        if frozenset((u, v)) not in edge_set
    ]
    return vertices, complement, k


vertices = [0, 1, 2, 3]
edges = [(0, 1), (0, 2), (1, 2)]
new_vertices, complement, k = clique_to_independent(vertices, edges, 3)
assert complement == [(0, 3), (1, 3), (2, 3)]
candidate = {0, 1, 2}
assert len(candidate) >= k
assert all(not (u in candidate and v in candidate) for u, v in complement)
print(complement)

输入采用合法无向简单图。哈希集合模型下构造成本O(n²+m)，输出补图最多含O(n²)条边，所占空间也为O(n²)。原图中的团{0,1,2}在补图中成为同样大小的独立集。

5. P与NP之间已知什么

$$ \mathrm P\subseteq\mathrm{NP} $$

已经能快速求解的问题，可以由验证器直接运行求解算法确认，证书可以为空。因此属于NP不意味着已经排除属于P。

P是否等于NP仍是未解决问题；Clay Mathematics Institute将其列为开放问题。若任意一个NP完全问题具有多项式时间算法，则所有NP问题都能通过归约获得多项式算法，从而P=NP。

写出一个指数时间算法，说明的是该算法的资源上界，不能排除存在另一种更快算法。NP完全性也不是“已经证明只能穷举”。

6. 困难问题的求解方法

选择方法时，可以先明确需要精确最优、可证明近似，还是尽快得到可行方案。

方法	保留或追求什么	需要注意
启发式算法	尽快找到质量较好的可行解	通常没有统一的最优性或近似比保证
近似算法	多项式时间，并提供明确的解质量保证	保证必须有证明，不是只看测试平均效果
快速精确算法	仍返回真正最优解	最坏情况时间可能仍是指数级
参数化算法	利用某个参数较小的特点	要说清参数是什么，以及时间怎样依赖它

启发式并不等于“输出是否可行都不知道”。例如可以始终保持方案可行，只是不保证它全局最优。已有的HEFT文章就是理解启发式调度的一个入口，但它处理的是带依赖与异构处理器的另一种模型，不是本文的单会议室区间选择。

6.1 用一个数理解近似保证

对非负目标值，采用 $\rho\ge1$ 的比值约定：最大化问题的 $\rho$ 近似保证可写为 $ALG\ge OPT/\rho$；最小化问题则写为 $ALG\le\rho OPT$。

例如，最大化问题的最优值是100，一个有2近似保证的算法至少要得到50。这个例子只解释保证的含义，不是在声称任意问题都存在2近似算法。

课件还提到PTAS。它是多项式时间近似方案，不是与P、NP相同意义的判定复杂性类。对最小化问题，给定误差参数 $\varepsilon>0$，要求得到至多 $(1+\varepsilon)OPT$ 的可行解；对每个固定的误差参数，时间关于输入规模是多项式。

但时间可能形如 $n^{O(1/\varepsilon)}$，误差要求很小时仍可能不可用，不能理解成“误差随便调小且始终很快”。参见 Cesati 与 Trevisan 对PTAS效率的说明。

6.2 “参数较小”需要有明确的时间表达式

固定参数可解的一种典型形式是：

$$ T(n,k)=f(k)n^c $$

其中 c 不随参数 k 改变。例如 $2^k n^2$ 的指数代价集中在 k 上；当 k 很小时可能有用，但不表示 k 任意大时仍高效。仅仅说“对每个固定 k，$n^k$ 是多项式”还不满足上述形式的要求。

穷举提供容易验证的精确基线；分支定界和剪枝可以跳过不可能改进答案的分支。是否改善最坏时间，要根据剪枝能保证排除多少搜索状态来分析。

7. 高级选读：竞争选址与PSPACE

普通优化寻找一份好方案；对抗问题要求面对对手的每次回应都维持收益保证。

展开竞争选址、保证收益、博弈树与递归代码

7.1 规则里增加了一个会回应的对手

课件第31页给出一个带顶点权重的图。两名玩家轮流选择尚未被选、且不与任何已选顶点相邻的顶点，获得自己所选顶点的权重；没有合法位置时游戏结束。

问题是：给定阈值 B，后手是否有一种策略，无论先手怎样行动，都能得到至少 B 的总收益？

注意三个区别：

选出的所有顶点合起来是独立集，但权重由实际选中它们的玩家分别获得。
不再是一个人一次性挑选最佳集合，而是双方轮流行动。
问的是“面对所有对手应对都能保证”，不是“存在某一局碰巧得到高分”。

7.2 先手不同，后手能拿到的收益也不同

先看一个补充的小例子：三个顶点连成路径 $u-v-w$，权重依次为2、9、2。

三顶点竞争选址博弈树：先手选中间会使后手无路可走，因此后手最坏保证收益为0

先手选择	后手还有什么可选	后手最终收益
u	w	2
v	没有合法顶点	0
w	u	2

因此，后手“某一局能得到2”是真的，但“保证至少得到2”是假的：先手可以直接选 v。

计算保证收益时，后手在自己的回合取最大值，先手的回合则考虑最不利于后手的选择，取最小值：

$$ \min(2,0,2)=0 $$

7.3 用递归核对课件中的10个顶点

课件使用一条10个顶点的路径，权重为：

10, 1, 5, 15, 5, 1, 5, 1, 15, 10

下面用递归计算后手的最坏保证收益。

from functools import lru_cache


def second_player_guarantee(weights):
    n = len(weights)
    blocked = []
    for v in range(n):
        mask = 1 << v
        if v > 0:
            mask |= 1 << (v - 1)
        if v + 1 < n:
            mask |= 1 << (v + 1)
        blocked.append(mask)

    @lru_cache(None)
    def solve(available, second_turn):
        if available == 0:
            return 0
        outcomes = []
        for v, weight in enumerate(weights):
            if available & (1 << v):
                remaining = available & ~blocked[v]
                future = solve(remaining, not second_turn)
                outcomes.append(future + (weight if second_turn else 0))
        return max(outcomes) if second_turn else min(outcomes)

    return solve((1 << n) - 1, False)


assert second_player_guarantee([2, 9, 2]) == 0
weights = [10, 1, 5, 15, 5, 1, 5, 1, 15, 10]
print(second_player_guarantee(weights))  # 20

available 用二进制位表示哪些顶点仍然合法。选择 v 后，清除 v 及相邻顶点的位；只有后手选择时才把权重计入后手收益。递归返回的是从当前状态开始的未来保证收益，因此缓存不需要记录已经获得的分数。

结果为20，与课件中的“可以保证20，但不能保证25”一致。程序处理路径图的小规模实例，缓存状态数最坏为指数级。

7.4 为什么课件会提到PSPACE

一般图上的竞争选址判定问题是PSPACE完全问题，课件在这里用它提示“策略问题”与“找一份候选方案”的不同；相关结论可参见 Kevin Wayne 的PSPACE讲义。

PSPACE关注多项式空间。搜索树可能有很多分支，但深度最多是顶点数量，可以按深度优先方式逐个探索，不需要同时保存整棵树。时间很长与空间很多是两种不同的资源消耗。

已知包含关系是 $\mathrm P\subseteq\mathrm{NP}\subseteq\mathrm{PSPACE}$；这些包含关系是否严格，仍涉及开放问题。

7.5 缓存程序与多项式空间搜索

上面的lru_cache保存已经求过的状态，用空间换时间，缓存最坏可能指数增长。PSPACE成员性可以使用不保留全局缓存的深度优先搜索：每次只探索一个分支，每层保存剩余顶点、回合和当前最好或最坏值。

一局至多选择n次，搜索深度至多n；每层的数据用多项式位数表示，因此总空间为多项式。总分支数仍可能指数增长。时间与空间需要分别计量。Princeton的PSPACE讲义给出了竞争选址的PSPACE完全性结论与归约思路。

8. 易错点

NP不是“Non-Polynomial”；NP-hard与NP-complete的差别在于是否还要求属于NP。证明困难性时归约由已知难问题指向待证明问题；正实例验证与全局最优性验证不同。近似保证来自对全部合法实例的论证，测试平均分不能替代这种保证。

9. 练习

练习1：概念判断

判断：NP表示非多项式；属于NP的问题都不属于P；一个指数算法证明问题不存在多项式算法；验证大小达到k的独立集就是验证最大独立集。

练习2：NP完全证明

已知B属于NP，且B≤p某个NP完全问题C，是否足够证明B为NP完全？应该补什么方向的归约？

练习3：优化与判定

如果能多项式计算最大独立集的最优值，怎样回答阈值k的判定？这解释了优化版的什么性质？

练习4：近似保证

最优值100，测试结果都≥90，是否证明2近似？有证明的2近似最大化算法至少应得到多少？

练习5：PTAS与参数

n^(1/ε)对每个固定ε是多项式，是否表示ε调得很小时依然容易运行？n^k是否属于固定参数形式f(k)n^c（c与k无关）？

练习6：保证收益

高级例三顶点路径权重改为4、1、7，先手选择左端、中间、右端时，后手分别得多少？是否保证至少4？

练习7：时间与空间

深度n、分支至多n的游戏树，为什么能用多项式空间逐分支遍历？给所有状态加缓存后还保持这一空间保证吗？

10. 参考答案

四句均不正确。NP为非确定性多项式时间，P包含在NP内；一个算法的上界不排除另一种算法；达到阈值的可行性不要求排除所有更大的解。
不足，容易的问题也能归约到困难问题。应从已知NP完全问题A构造A≤pB，再结合B∈NP。
求出最优值M，比较M≥k即可。优化版能够解决NP完全判定版，所以在相应求解归约意义下是NP-hard。
有限测试未覆盖全部合法实例。2近似保证ALG≥OPT/2，因此最优100时至少50；其他实例按各自OPT计算。
不表示，指数1/ε可能很大。n^k的次数随k变化，不是固定参数可解要求的统一常数次数形式。
依次7、0、4，最坏保证min(7,0,4)=0，不能保证至少4。
深度优先只保存一条路径及每层的局部数据；若每层是多项式大小，总空间也是多项式。保存所有已访问状态的缓存可能指数增长。

11. 后续学习与资料

专题入口：导论；上一篇：图优化。后续可学习3-SAT到图问题的归约、分支定界、具体近似算法与固定参数算法。

课程来源：Introduction第21至25页的困难问题方法、第30至31页的独立集与竞争选址。权威补充资料：

Stephen Cook：P versus NP：判定、验证与多项式归约。
Clay：P与NP问题状态。
Michael Dinitz：NP-Completeness II：团到独立集的归约。
Cesati与Trevisan：PTAS效率。
Kevin Wayne：PSPACE。

原有三顶点、10顶点路径、保证收益代码和相关习题在本篇保留。