计算复杂性理论中的多项式时间归约 我们先从基础概念开始。多项式时间归约是计算复杂性理论中用于比较问题计算难度的一种核心方法。它的核心思想是：如果问题A可以“高效地”转化为问题B，那么B至少和A一样难。这里的“高效”特指在多项式时间内完成转化。 第一步：形式化定义 更精确地说，设A和B是两个判定问题（即答案是“是”或“否”的问题）。一个从A到B的多项式时间归约是一个多项式时间可计算函数 f：Σ* → Σ* （其中Σ是字母表），使得对于任意输入x，x ∈ A 当且仅当 f(x) ∈ B。 第二步：理解其内涵 这个定义意味着什么呢？ 转化函数f ：存在一个算法，对于任何输入x，它能在关于x长度（|x|）的多项式时间内输出f(x)。 等价性 ：函数f将问题A的“是”实例精确地映射到问题B的“是”实例，同时将“否”实例映射到“否”实例。因此，要判断x是否属于A，你可以先计算f(x)，然后判断f(x)是否属于B。由于f是多项式时间可计算的，如果B本身也能在多项式时间内求解，那么A也就能在多项式时间内求解了。 第三步：归约与复杂性类的关系 多项式时间归约最重要的应用之一是定义复杂性类的“难度”概念。最重要的概念是 NP-困难 和 NP-完全 。 如果对于NP中的每一个问题L，都存在一个到问题B的多项式时间归约，则称问题B是 NP-困难的 。 如果一个问题B既是NP-困难的，又本身属于NP类，则称B是 NP-完全的 。 第四步：一个经典的归约例子 考虑从 布尔可满足性问题 到 3-SAT问题 的归约。 问题A（SAT） ：给定一个布尔公式，判断是否存在一个变量赋值使其为真。 问题B（3-SAT） ：给定一个合取范式（CNF）公式，且每个子句恰好包含三个文字，判断是否存在一个变量赋值使其为真。 归约函数f的工作方式如下：它将任意一个SAT实例（一个布尔公式）转化为一个等价的3-SAT实例。 首先，使用标准方法（例如引入新变量）将原始公式转化为一个CNF公式。 然后，对于CNF中每个子句，如果它包含的文字数k不等于3，则将其转化为一组等价的、每个都恰好包含3个文字的子句。例如，一个单文字子句 (x) 可以转化为 (x ∨ y ∨ z) ∧ (x ∨ ¬y ∨ z) ∧ (x ∨ y ∨ ¬z) ∧ (x ∨ ¬y ∨ ¬z)，通过引入新变量y和z，并构造一组子句来强制x必须为真。对于k>3的子句，也可以通过引入新变量链式地分解为多个三文字子句。 这个转化过程可以在多项式时间内完成，并且原公式可满足当且仅当新生成的3-CNF公式可满足。这就构成了一个多项式时间归约。 第五步：多项式时间归约的类型 归约可以根据其“强度”进一步细分： 卡普归约 ：这就是我们上面定义的通用形式，也称为“多项式时间多一归约”。它要求归约函数f是单值的。 图灵归约 ：这是一种更强的归约概念。它允许在归约过程中将问题B作为一个“子程序”或“谕示”多次调用。多项式时间的图灵归约在定义更高级的复杂性类（如多项式层级）的完全性时非常重要。 总结 多项式时间归约是复杂性理论的基石。它提供了一个严格的框架来证明问题的相对难度，是理解P与NP问题以及整个计算复杂性图谱的关键工具。通过证明一个已知的NP完全问题（如3-SAT）可以归约到另一个问题，我们就证明了后者的NP难度。