我在算法课程中阅读了 Garey 和 Johnson 所著的Computers and Intractability - A Guide to the Theory of NP-Completeness 一书；然而，在一年后复习这些材料时，我意识到我从来没有真正理解过库克定理。
关于证明，我理解为什么 SAT 首先被证明是 NP 的（NP 完全的第一个要求），但是我正在努力通过显示“遗传”多项式下的“其他”NP 完全问题的技术性转换为 SAT。
我想知道是否有人可以以更淡化的方式解释这一点，这可能会澄清对本节的额外阅读。
SAT 是 NP-hard 的证明（即，从每个 NP 问题到 SAT 都有多项式时间减少）是不平凡的。我将尝试直观地了解它是如何工作的，但我不会尝试详细介绍所有细节。为此，您可能需要查阅教科书。
让我们从任何 NP 语言 L 开始。根据定义，L 是一种 NP 语言这一事实意味着语言 L 存在一个非确定性的多项式时间图灵机 M。这意味着机器 M 接受一个字符串 w，如果并且仅当 w 属于 L，并且除此之外，M 的运行时间是某个多项式 p(n)。从 L 到 SAT 的简化将通过表明您可以构建一个命题公式来实现，该公式基本上模拟了 M 在某些特定字符串 w 上的操作。该公式具有 M 接受 w（即 w 属于 L）的性质当且仅当得到的命题公式是可满足的。
完全不清楚是否有可能做到这一点。为了了解它是如何工作的，我们将使用一种标准技术来减少涉及 TM 的问题。想想 M 对字符串 w 的操作。由于 M 是图灵机，当我们以 w 启动 M 时，它以写在磁带上的 w 开始（被无限多的空白包围），在某些状态 q 0，并且磁带头在 w 的第一个字符上。图灵机的每一步都会使机器向左或向右移动磁带头，以替换磁带头下方的符号，以及向左或向右移动磁带头。
在 TM 的每一步之前，我们可以拍摄机器状态的“快照”。该快照将包括从两侧修剪掉无数空白后的磁带、磁带头的位置以及 TM 的当前状态。这个“快照”更恰当地称为机器的瞬时描述或ID。您可以将其视为（磁带内容、状态、位置）的元组。
因为 M 是一个多项式时间 NTM，我们知道它在输入字符串 w 上运行时不能运行超过 p(|w|) 步，其中 p 是某个多项式。因此，当 M 运行时，计算最多将有 p(|w|) + 1 个瞬时描述，每个步骤一个。因此，您可以将 M 的任何执行视为一系列此 ID，一个接一个地写出，如 (tape0, state0, position0), (tape1, state1, position1), ..., (tapeK, stateK,位置 K)。
关于这些 ID，有两个观察结果。首先，这些 ID 不能是完全任意的。我们知道第一个 ID 将是什么 - 它将是磁带保存 w 的 ID，状态为 q 0，并且磁带头位于字符串 w 的开头。因此，基于 TM 第一步可以做出的每个不确定性选择，第二个 ID 的选择只有少数几种。类似地，第三个 ID 的选择数量是有限的，因为该 ID 必须从某个合法的第二个 ID 开始并应用 TM 的一个移动来形成。更一般地，每个 ID 必须遵循从前一个 ID 开始的合法 TM 移动。
其次，请注意，如果 M 接受 w，则存在一些可能的 ID 链，使得链中的最后一个 ID 将处于状态，其中状态是机器的接受状态。相反，如果 M 不接受 w，那么任何可能的 ID 链都不会合法地以机器处于接受状态结束。
因此，从 L 到 SAT 的简化本质上是通过建立一个巨大的命题公式来实现的。每个变量对应于链中某个 ID 的一部分（某个特定磁带单元的内容，或者机器将处于什么状态，或者磁带头在哪里）。然后，该公式对有关 ID 的规则进行编码：第一个 ID 必须是机器启动状态 q 0磁带头扫描输入字符串 w 的第一个字符，每个 ID 必须跟在前一个 ID 之后，等等。公式的最后一部分 - 机器必须以接受状态结束。实际上建立所有这些公式是非常棘手的（这就是为什么你应该看一本教科书）。但是，最终结果是，如果公式可满足，则有一系列 ID 表明 M 接受 w（因此 w 在 L(M) 中），如果不可满足，则 M 无法接受 w。
希望这可以帮助！