数据结构与算法 / 系统课时
多项式时间归约
多项式时间归约
面对一个新问题时,直接判断它是否容易求解往往很困难。多项式时间归约提供了一种比较工具:把已知问题的实例高效转换成目标问题实例,并确保转换前后的“是/否”答案完全一致。
学习目标
- 准确定义多项式时间归约及其答案保持条件。
- 判断归约方向,并解释“谁不比谁更容易”。
- 使用独立集到顶点覆盖的转换完成一个可验证示例。
归约的目标与方向
设 A 和 B 都是判定问题。若存在一个多项式时间可计算的转换函数 ,使任意实例 都满足“ 属于 A 当且仅当 属于 B”,则记作 A ≤p B。
这个方向表示:只要会解决 B,就能先计算 ,再借助 B 的算法解决 A。因此,B 至少和 A 一样难。证明目标问题 B 是 NP 困难时,应从一个已知 NP 困难问题 A 出发,构造 A ≤p B,而不是反过来。

归约必须同时满足两个条件:转换本身在多项式时间内完成;转换对所有合法实例都保持答案。只展示若干样例结果相同,不能替代一般性证明。
构造归约的步骤
构造一个可靠归约时,可以按以下顺序推进:
- 明确源问题 A 和目标问题 B 的实例格式及判定条件。
- 给出转换函数 ,说明如何从 A 的任意实例构造 B 的实例。
- 分别证明“若 A 为是,则 B 为是”和“若 B 为是,则 A 为是”。
- 分析转换所需时间,确认它关于输入规模是多项式级。
一个经典关系是独立集与顶点覆盖。对图 ,集合 是独立集,当且仅当补集 是顶点覆盖。因此,独立集实例 可以转换为顶点覆盖实例 。这给出 Independent Set ≤p Vertex Cover,转换只需计算顶点数并做一次减法。
完整可运行示例
下面的程序在一个小图上验证上述等价关系。枚举所有顶点子集只是为了演示两个判定问题的答案一致;真正的归约步骤仅是把参数 转换为 。
from itertools import combinations
from typing import Iterable
Edge = tuple[int, int]
def is_independent_set(vertices: set[int], edges: set[Edge]) -> bool:
return all(not ({u, v} <= vertices) for u, v in edges)
def is_vertex_cover(vertices: set[int], edges: set[Edge]) -> bool:
return all(u in vertices or v in vertices for u, v in edges)
def has_independent_set(
vertex_count: int,
edges: set[Edge],
size: int,
) -> bool:
for group in combinations(range(vertex_count), size):
if is_independent_set(set(group), edges):
return True
return False
def has_vertex_cover(
vertex_count: int,
edges: set[Edge],
size: int,
) -> bool:
for group in combinations(range(vertex_count), size):
if is_vertex_cover(set(group), edges):
return True
return False
def reduce_independent_set_to_vertex_cover(
vertex_count: int,
independent_size: int,
) -> int:
# 参数转换 t = |V| - k 保持两个问题的答案一致。
return vertex_count - independent_size
def run_case(
vertex_count: int,
edges: set[Edge],
independent_size: int,
) -> None:
cover_size = reduce_independent_set_to_vertex_cover(
vertex_count,
independent_size,
)
independent_answer = has_independent_set(
vertex_count,
edges,
independent_size,
)
cover_answer = has_vertex_cover(
vertex_count,
edges,
cover_size,
)
print(
f"实例 (G, k={independent_size}) -> "
f"(G, t={cover_size})"
)
print(f"独立集实例答案: {independent_answer}")
print(f"顶点覆盖实例答案: {cover_answer}")
print(f"答案保持一致: {independent_answer == cover_answer}")
def main() -> None:
vertex_count = 5
edges = {(0, 1), (1, 2), (2, 3), (3, 4)}
run_case(vertex_count, edges, independent_size=3)
print()
run_case(vertex_count, edges, independent_size=4)
if __name__ == "__main__":
main()运行命令:
python polynomial_reduction.py预期输出:
实例 (G, k=3) -> (G, t=2)
独立集实例答案: True
顶点覆盖实例答案: True
答案保持一致: True
实例 (G, k=4) -> (G, t=1)
独立集实例答案: False
顶点覆盖实例答案: False
答案保持一致: True示例中的穷举判定需要指数时间,但这不影响归约有效性,因为归约函数只计算 ,其时间复杂度为 ;若还需要复制图结构,整体转换时间为 。
证明模板与常见错误
要证明 B 是 NP 完全问题,通常分成两部分:先证明 B 属于 NP,再选择一个已知 NP 完全问题 A,构造 A ≤p B。仅证明 A ≤p B,只能说明 B 至少和 A 一样难,不能自动得到 B 属于 NP。
| 错误 | 问题所在 | 修正方式 |
|---|---|---|
| 构造 B ≤p A 来证明 B 很难 | 方向只能说明 A 至少和 B 一样难 | 从已知困难的 A 归约到 B |
| 只证明“是”实例能转换 | 可能把“否”实例错误地变成“是”实例 | 证明双向等价 |
| 转换后再调用指数算法 | 把求解过程误当成归约过程 | 单独分析实例转换函数 |
| 只用几个样例测试 | 样例不能覆盖所有输入 | 给出对任意实例成立的证明 |
本课练习
练习 1:利用“团与独立集互为补图中的对应结构”,写出 Clique ≤p Independent Set 的实例转换。验收条件是明确图如何转换、参数是否变化,并证明答案双向保持。
练习 2:有人为了证明顶点覆盖很难,写出 Vertex Cover ≤p Independent Set。判断这个方向能否达到证明目标,并改写成合适的论证方向。
本课总结
- A ≤p B 表示可借助 B 的求解器解决 A,因此 B 至少和 A 一样难。
- 合法归约必须在多项式时间内完成,并对全部实例保持“是/否”答案。
- NP 完全性证明通常需要同时给出“属于 NP”和“已知 NP 完全问题归约到目标问题”。
下一课预告
下一阶段将继续研究复杂性边界下的算法设计,重点关注当精确多项式时间算法不可得时,如何通过随机化或近似策略获得可证明的效率与解质量。