您如何证明SAT已完成？

Question

本质上，您如何证明SAT是NP完整的？

我知道NP完整的含义，因此我不需要对此进行解释。

我想知道的是，您如何知道一个问题（例如SAT）是NP的完整，而无需求助于其他问题，例如哈密顿问题或其他问题。

Answer 1

我相信3个序言最初是从KARP的论文中概述的更普遍的满意度中缩小的 21 NP完整问题.

维基百科有描述 关于如何显示可满足性是NP的完整性，这一结果称为 Cook-Levin定理. 。该证明的想法是证明任何多项式时间非确定的图灵机可以建模为具有多项式大小的布尔表达。布尔表达式具有表示图灵机的有效配置空间的术语：磁带头在哪里，当前状态是什么，磁带上写了哪些符号以及哪些过渡在每个位置都是有效的。由于NTM会在多项式时间中停止，因此配置空间是有界的，我们可以制作（大）多项式表达来表示它。