14.2 补充：NP 完全性与归约

前置：复杂度分析与贪心算法。这一节不试图证明 P 是否等于 NP，而是建立四个复杂度类别、归约方向，以及遇到 NP-hard 优化问题时可采用的工程策略。

旅行商究竟是哪一个问题

考虑城市数可变、非负整数距离以二进制编码的一般 TSP 实例：“找最短巡回路线”是优化问题；“是否存在总长度不超过 K 的巡回路线”是判定问题。两者关系紧密，复杂度标签却不能混写：

• TSP 判定版属于 NP-complete；
• TSP 优化版属于 NP-hard，通常不称为 NP-complete，因为 NP 按判定问题定义。

同一个故事常有判定、搜索、计数和优化版本。讨论复杂度前先写清输入、输出与问题版本，否则一句“这个问题是 NP 完全的”可能连对象都没说对。

P、NP、NP-complete 与 NP-hard

P 是可由确定性算法在多项式时间内求解的判定问题集合。NP 中的“是”实例有长度不超过输入规模多项式的证书，可由确定性算法在多项式时间内验证；“否”实例不能有通过验证的证书。已知 P 包含于 NP；P 是否等于 NP仍未解决。这里的规模按有限编码的长度计数，不能把任意精度实数当成一个免费输入单元。

一个判定问题 B 是 NP-complete，需要同时满足：

1. B 属于 NP；
2. NP 中每个问题都能在多项式时间内归约到 B。

NP-hard 只要求至少具备这种归约意义上的困难度。它可以是优化问题，也可能不属于 NP，甚至可能不可判定。因此 NP-complete 是 NP 与 NP-hard 的交集，不是所有“运行很慢的问题”的别名。

“目前没找到多项式算法”不能证明 NP-hard。严格结论需要已有定理或归约证明。

归约方向不能写反

记作：

A <=p B

本节对判定问题使用多项式时间多对一归约：能把 A 的任意实例转换成 B 的一个实例，并保留 yes/no 答案。若 B 有多项式算法，A 也随之可解。

要证明新问题 B 是 NP-hard，应从一个已知 NP-hard 问题 A 归约到 B。把 B 归约到 A 只说明 B 不比 A 更难，无法证明 B 的下界。

归约还必须保留答案：

A 实例答案为 yes  <=>  转换后的 B 实例答案为 yes

只说“两个问题看起来相似”不够。

启发式与有界近似不是一回事

下面的最近邻 TSP 每次走向当前最近的未访问城市。距离矩阵必须为非负整数方阵，对角线为 0；允许不对称，也不要求三角不等式。start 是整数城市编号。空矩阵只接受默认起点 0，返回 ([], 0)；单城市返回 ([0, 0], 0)。它是启发式：对一般距离矩阵没有固定近似比保证。函数仍应验证输入合同，不能拿一个示例路线暗示全局最优。

def tsp_nearest_neighbor(distance, start=0):
    city_count = len(distance)
    if not isinstance(start, int):
        raise TypeError("start must be an integer")
    if city_count == 0:
        if start != 0:
            raise IndexError("empty matrix requires the default start")
        return [], 0
    if not 0 <= start < city_count:
        raise IndexError("start city is out of range")
    if any(len(row) != city_count for row in distance):
        raise ValueError("distance matrix must be square")
    if any(not isinstance(value, int) or value < 0
           for row in distance for value in row):
        raise ValueError("distances must be non-negative integers")
    if any(distance[city][city] != 0 for city in range(city_count)):
        raise ValueError("diagonal distances must be zero")

    unvisited = set(range(city_count))
    unvisited.remove(start)
    route = [start]
    total = 0
    current = start

    while unvisited:
        next_city = min(
            unvisited,
            key=lambda city: (distance[current][city], city),
        )
        total += distance[current][next_city]
        route.append(next_city)
        unvisited.remove(next_city)
        current = next_city

    total += distance[current][start]
    route.append(start)
    return route, total

sample = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0],
]
assert tsp_nearest_neighbor(sample) == ([0, 1, 3, 2, 0], 80)

结果 80 恰好是这份小样例的最优值，但这不构成最近邻算法的一般保证。评价启发式应同时给出基准实例、运行预算和解质量。比如 [[0,1,2],[1,0,100],[2,1,0]] 从 0 出发会得到 0→1→2→0、成本 103，而 0→2→1→0 只需 4；把 100 增大还能继续拉大差距。此例利用了合同允许的不对称距离。算法含矩阵检查共 Θ(n²) 时间，额外空间 O(n)，相同距离按城市编号决胜，不修改输入。

顶点覆盖的 2-近似

无权无向图顶点覆盖要求选择一组顶点，使每条边至少有一个端点被选。反复取一条尚未覆盖的边，把它的两个端点都加入结果，等价于先构造一个极大匹配，再取匹配边的所有端点。“极大”指不能再加入边，“最大”才是所有匹配中边数最多；这里不需要求最大匹配。输入是邻接映射，邻接集合应可重复遍历，顶点需具有稳定、满足自反性的哈希与相等关系。每个邻接记录都被当成一条无向边，重复记录会合并，允许只列一个方向或省略无出边顶点的键，自环则抛 ValueError。

def approx_vertex_cover(graph):
    edges = set()
    for vertex, neighbors in graph.items():
        for neighbor in neighbors:
            if neighbor == vertex:
                raise ValueError("self-loops are not supported")
            edges.add(frozenset((vertex, neighbor)))

    selected = set()
    for edge in edges:
        left, right = tuple(edge)
        if left not in selected and right not in selected:
            selected.update((left, right))
    return selected

def is_vertex_cover(graph, selected):
    return all(
        vertex in selected or neighbor in selected
        for vertex, neighbors in graph.items()
        for neighbor in neighbors
    )

graph = {
    0: [1, 2],
    1: [0, 2, 3],
    2: [0, 1, 3],
    3: [1, 2],
}
cover = approx_vertex_cover(graph)
assert is_vertex_cover(graph, cover)

匹配中的每条边都要求任意顶点覆盖至少选一个端点，因此最优解大小至少是匹配边数。算法为每条匹配边选两个端点，所以结果不超过最优值的两倍。该证明只保证未加权的顶点数量，不能直接用于顶点权重。实现先收集边，再扫描一次；若输入含 V 个顶点和 R 条邻接记录、去重后为 E 条边，期望时间 O(V+R)、额外空间 O(V+E)，假设哈希操作为常数成本。集合迭代次序可能改变所选匹配，但不改变 2-近似保证。

面对 NP-hard 问题时怎么选

情况	可考虑的方法	必须说明
实例很小	枚举、分支定界、剪枝	仍可能枚举指数或阶乘数量的候选
需要最优解	ILP/SAT/CP 等求解器或专用精确算法	超时与最优性证书
可接受误差	有证明的近似算法	近似比和适用前提
数据有小参数	参数化算法	指数部分依赖哪个参数
只需可用方案	启发式、局部搜索、元启发式	没有最优性保证
实例有特殊结构	利用树宽、平面性或业务约束	结构是否始终成立

NP-hard 不等于所有实例都难。实际数据可能很小或带有额外结构；求解器也常能处理规模可观的实例。NP-hard 也没有无条件证明某个问题必须花指数时间；若 P≠NP，才可排除其一般情形的多项式精确算法。复杂度结论不替代对真实实例分布的测量。

动手检查归约与保证

1. 用自己的话解释为什么“已知 A 很难，且 B <=p A”不能证明 B 很难。
2. 把顶点覆盖与独立集的补集关系写成双向的 yes/no 证明。
3. 为 6 个城市暴力枚举 TSP，与最近邻结果比较，主动寻找反例。
4. 从极大匹配证明顶点覆盖 2-近似的上下界。
5. 给一个优化问题分别写出判定版与证书验证器。

区分困难度与求解承诺

NP 完全性提供的是可验证的归类方法，不是“代码写不出来”的安慰。先固定问题版本，再检查成员关系与归约方向；进入工程决策后，还要区分精确、近似和启发式三种不同承诺。

下一节换一个视角：摊还分析研究的不是问题本身有多难，而是一串操作中偶尔昂贵的步骤如何被整体成本吸收。