我在算法课程中阅读了Garey和Johnson的《计算机与难处理性——NP完全性理论指南》一书；然而，一年后，当我复习这些材料时，我意识到我从来没有真正理解过库克定理。
关于证明，我理解为什么SAT首先被证明是NP优先的（NP完全的第一个要求），但我正在努力克服证明"其他"NP完全问题在"遗传"多项式变换下为SAT的技术细节。
我想知道是否有人可以用一种淡化的方式来解释这一点，这可能会澄清对本节的额外解读。
SAT是NP难的证明（即从每个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开始（被无限多的空格包围），在某种状态下q0，磁带头在w的第一个字符上。图灵机的每一步都会使机器向左或向右移动磁带头，以替换磁带头下的符号，以及向左或向右移动磁带磁头。
在TM的每一步之前，我们都可以拍摄机器状态的"快照"。该快照将包括从两侧剪下无限多空白后的磁带、磁带头的位置和TM的当前状态。此"快照"更恰当地称为机器的瞬时描述或ID。您可以将其视为（磁带内容、状态、位置）的元组。
因为M是多项式时间NTM，我们知道当在输入字符串w上运行时，它不能运行超过p（|w|）步，其中p是某个多项式。因此，当M运行时，计算将最多有p（|w|）+1个瞬时描述，每个步骤一个。因此，您可以将M的任何执行视为一系列这个ID，一个接一个地写出来，如（tape0，state0，position0），（tape1，state1，position1）。。。，（磁带K、状态K、位置K）。
关于这些ID，有两个观察结果。首先，这些ID不能完全是任意的。我们知道第一个ID将是什么-它将是一个ID，其中磁带保持w，状态为q0，磁带头位于字符串w的开头。因此，根据TM可以为其第一步做出的每个不确定的选择，第二个ID只有几个可能的选择。类似地，第三个ID的选择数量是有限的，因为该ID必须通过从某个合法的第二个ID开始并应用TM的一个移动来形成。更一般地说，每个ID必须从前一个ID开始的合法TM移动。
其次，请注意，如果M接受w，则存在一些可能的ID链，使得链中的最后一个ID将处于该状态，其中该状态是机器的接受状态。相反，如果M不接受w，那么任何可能的ID链都不会以机器处于接受状态而合法结束。
因此，从L到SAT的约简本质上是通过建立一个巨大的命题公式来实现的。每个变量对应于链中某个ID的某个片段（或者是某个特定磁带单元的内容，或者机器将处于什么状态，或者磁带头将在哪里）。然后，该公式对有关ID的规则进行编码：第一个ID必须是机器启动状态q0的ID，磁带头扫描输入字符串w的第一个字符，每个ID必须遵循前一个ID，等等。公式还有最后一部分-机器必须以接受状态结束。事实上，建立所有这些公式是非常棘手的（这就是为什么你应该看教科书）。然而，最终结果是，如果公式是可满足的，则有一系列ID表明M接受w（因此w在L（M）中），如果它不可满足，则M无法接受w。
希望这能有所帮助！