数据结构与算法 / 系统课时

多项式时间归约

多项式时间归约

面对一个新问题时,直接判断它是否容易求解往往很困难。多项式时间归约提供了一种比较工具:把已知问题的实例高效转换成目标问题实例,并确保转换前后的“是/否”答案完全一致。

学习目标

  • 准确定义多项式时间归约及其答案保持条件。
  • 判断归约方向,并解释“谁不比谁更容易”。
  • 使用独立集到顶点覆盖的转换完成一个可验证示例。

归约的目标与方向

设 A 和 B 都是判定问题。若存在一个多项式时间可计算的转换函数 ff,使任意实例 xx 都满足“xx 属于 A 当且仅当 f(x)f(x) 属于 B”,则记作 A ≤p B。

这个方向表示:只要会解决 B,就能先计算 f(x)f(x),再借助 B 的算法解决 A。因此,B 至少和 A 一样难。证明目标问题 B 是 NP 困难时,应从一个已知 NP 困难问题 A 出发,构造 A ≤p B,而不是反过来。

多项式时间归约的方向与答案保持

归约必须同时满足两个条件:转换本身在多项式时间内完成;转换对所有合法实例都保持答案。只展示若干样例结果相同,不能替代一般性证明。

构造归约的步骤

构造一个可靠归约时,可以按以下顺序推进:

  1. 明确源问题 A 和目标问题 B 的实例格式及判定条件。
  2. 给出转换函数 ff,说明如何从 A 的任意实例构造 B 的实例。
  3. 分别证明“若 A 为是,则 B 为是”和“若 B 为是,则 A 为是”。
  4. 分析转换所需时间,确认它关于输入规模是多项式级。

一个经典关系是独立集与顶点覆盖。对图 G=(V,E)G=(V,E),集合 SS 是独立集,当且仅当补集 V−SV-S 是顶点覆盖。因此,独立集实例 (G,k)(G,k) 可以转换为顶点覆盖实例 (G,∣V∣−k)(G,|V|-k)。这给出 Independent Set ≤p Vertex Cover,转换只需计算顶点数并做一次减法。

完整可运行示例

下面的程序在一个小图上验证上述等价关系。枚举所有顶点子集只是为了演示两个判定问题的答案一致;真正的归约步骤仅是把参数 kk 转换为 ∣V∣−k|V|-k。

python
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()

运行命令:

bash
python polynomial_reduction.py

预期输出:

text
实例 (G, k=3) -> (G, t=2)
独立集实例答案: True
顶点覆盖实例答案: True
答案保持一致: True

实例 (G, k=4) -> (G, t=1)
独立集实例答案: False
顶点覆盖实例答案: False
答案保持一致: True

示例中的穷举判定需要指数时间,但这不影响归约有效性,因为归约函数只计算 t=∣V∣−kt=|V|-k,其时间复杂度为 O(1)O(1);若还需要复制图结构,整体转换时间为 O(∣V∣+∣E∣)O(|V|+|E|)。

证明模板与常见错误

要证明 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 完全问题归约到目标问题”。

下一课预告

下一阶段将继续研究复杂性边界下的算法设计,重点关注当精确多项式时间算法不可得时,如何通过随机化或近似策略获得可证明的效率与解质量。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

多项式时间归约

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通