4.1. NP 完全性证明¶

为了启动能够证明问题是 NP 完全的过程，我们只需要证明一个问题 \(H\) 是 NP 完全的。 之后，要证明任何问题 \(X\) 是 NP 困难的，我们只需把 \(H\) 归约为 \(X\)。 做 NP 完全性证明时，千万不要把这种归约的方向搞反！ 如果我们把候选问题 \(X\) 归约为已知困难问题 \(H\)，这意味着我们用 \(H\) 作为求解 \(X\) 的一步。 这只不过说明我们找到了一种（已知的）困难的求解 \(X\) 的方式。 然而，当我们把已知困难问题 \(H\) 归约为候选问题 \(X\) 时，那意味着我们用 \(X\) 作为求解 \(H\) 的一步。 而我们既然知道 \(H\) 是困难的，那就意味着 \(X\) 也必然是困难的 （因为如果 \(X\) 不困难，那么 \(H\) 也不会困难）。

因此，要让整套理论起步，关键的第一步是找到一个 NP 困难的问题。 关于某个问题是 NP 困难（并且因为它在 NP 中，因而也是 NP 完全）的第一个证明是由 Stephen Cook 完成的。 凭借这一成就，Cook 赢得了第一届图灵奖——这是计算机科学领域最接近诺贝尔奖的奖项。 Cook 用来作为"老祖宗"的 NP 完全问题叫做 SATISFIABILITY （简称 SAT ）。

布尔表达式 由 布尔变量 用 AND（\(\cdot\)）、OR（\(+\)）和 NOT 运算符组合而成 （要取布尔变量 \(x\) 的否定，我们写作 \(\overline{x}\)）。 文字 是布尔变量或其否定。 子句 是一个或多个文字用 OR 连接而成。 设 \(E\) 是变量 \(x_1, x_2, ..., x_n\) 上的布尔表达式。 我们把 合取范式 （CNF）定义为用 AND 连接一系列子句写成的布尔表达式。 例如，

就是 CNF，并且包含三个子句。 现在我们可以定义问题 SAT 了。

Cook 证明了 SAT 是 NP 困难的。 详细解释 Cook 的证明超出了本课程的范围。 但我们可以把它简要概括如下。 任何判定问题 \(F\) 都可以改述为某个语言接受问题 \(L\)：

也就是说，如果判定问题 \(F\) 对输入 \(I\) 给出 YES， 那么就存在一个语言 \(L\) 包含字符串 \(I'\)，其中 \(I'\) 是输入 \(I\) 的某种适当转换。 反过来，如果 \(F\) 对输入 \(I\) 给出答案 NO， 那么 \(I\) 的转换版本 \(I'\) 就不在语言 \(L\) 中。 例如，识别给定图是否存在代价小于 \(k\) 的 TRAVELING SALESMAN 解法， 等价于识别该图的字符串表示是否属于这样的语言： 该语言由所有对应 TRAVELING SALESMAN 答案为 YES 的图的字符串组成。

图灵机是一种简单的计算模型，用来编写作为语言接受器的程序。 存在一台"通用"图灵机，它以某个图灵机的描述和一个输入字符串作为输入，并返回该机器在该字符串上的执行结果。 （下一步是证明中的关键一步。） 这个图灵机反过来可以转换为一个布尔表达式， 使得该表达式可满足当且仅当该图灵机对该字符串给出 ACCEPT。 Cook 在其证明中使用了图灵机： 因为它们足够简单，使他能够建立起从图灵机到布尔表达式的这一转换， 同时又足够强大，能够计算普通计算机能计算的任何函数。 这一转换的意义在于，任何能由图灵机执行的判定问题都可以转换为 SAT 。 因此， SAT 是 NP 困难的。

要证明判定问题 \(X\) 是 NP 完全的， 我们首先证明 \(X\) 在 NP 中（这通常很容易，通常只需给出一个合适的多项式时间非确定性算法）， 然后证明 \(X\) 是 NP 困难的。 为了证明 \(X\) 是 NP 困难的，我们选择一个已知的 NP 完全问题，比如 \(A\)。 我们描述一个多项式时间转换，将 \(A\) 的 任意 实例 \(I\) 变为 \(X\) 的一个实例 \(I'\)。 然后我们描述一个多项式时间转换，将问题 \(X\) 中 \(I'\) 的解（称之为 \(SLN'\)）转换为 \(SLN\)， 使得 \(SLN\) 是问题 \(A\) 中 \(I\) 的解。

术语 ：证明一个问题为 NP 完全，从根本上说涉及从已知 NP 完全问题到所讨论问题的归约。 当然，把它搞反只会意味着用一个已知困难问题去解一个可能困难也可能不困难的问题。 注意，有时术语会以任一种顺序使用。 有些人说我们"从（ FROM ）已知 NP 完全问题"归约"到（ TO ）所讨论的问题"； 另一些人说我们"归约到（ TO ）所讨论的问题"且"从（ FROM ）已知 NP 完全问题"。 这两种说法意思相同，但不同的措辞有时会让人困惑。

下面的练习给你一个机会，让你重现 NP 完全性证明的标准模板。 这将有助于确认你是否理解这一过程。

下面的模块展示了一些已知的 NP 完全问题，以及一些它们为 NP 完全的证明。 各种证明会像这里显示的那样把这些问题联系起来：