如何将 3-SAT 简化为独立集？
Ar2*_*254 4 algorithm graph np independent-set sat
我正在从这里（第 8、9 页）阅读有关 NP 硬度的信息，并且在注释中，作者将 3-SAT 形式的问题简化为可用于解决最大独立集问题的图形。
在示例中，作者将以下 3-SAT 问题转换为图形。3-SAT 问题是：
(a ? b ? c) ? (b ? ~c ? ~d) ? (~a ? c ? d) ? (a ? ~b ? ~d)
生成的等效图为：
作者指出，如果满足以下条件，则两个节点通过边连接：
- 它们对应于同一子句中的文字
- 它们对应于一个变量及其逆。
我无法理解作者是如何提出这些规则的。
- 为什么我们需要在变量和它的逆之间画边？
- 假设有两个子句，子句 1 有 (a,b,~c) 和子句 2 有 (~a,b,c) 连接子句 1 到子句 2，为什么我们必须连接 a 和 ~a？为什么我们不能将 a（第 1 条）与 c（第 2 条）连接起来？
我认为可以解决问题的是还原概念。假设你熟悉一个问题说 X(即 3-SAT)[什么意思熟悉？你知道解决 X 的难度有多大]。此外，您目前正在分析另一个新问题，例如 Y（即独立集）...
你对 X 的了解如何帮助你想出 Y？如果你能找到它们之间的关系（即归约），那么你可以使用关于 X 到 Y 的知识。诸如“Y 比 X 难”或“Y 和 X 一样难”之类的东西。因此，该解决方案想要做的是找到两个问题之间的关系。
在可计算性理论和计算复杂性理论中，归约是一种将一个问题转化为另一个问题的算法。从一个问题到另一个问题的简化可以用来表明第二个问题至少和第一个问题一样困难。
你在这里提到的两条规则就是所有这些（即关系）。
- 您不能同时选择一条边的两个顶点。此外，您不能同时设置变量及其否定为 TRUE。
- 您必须在子句中有一个 TRUE 变量。同样为了最大化所选顶点的数量，您必须从每个子句中选择一个节点。
这显示了这些规则的来源。
PS：这里提到的作为解决 3-SAT to Independent Set 问题的证明并不准确。这个解释只是为了让你更深入地了解证明想要做什么程序。证明留给学术笔记。
减少的另一件重要事情是它自己的时间。另一方面，减少时间（即将 X 实例转换为 Y 实例所需的时间）必须小于 X 问题时间（因为它支配 X 解决时间）。
也有一些符号表明，X < Y以其他时间顺序作为 的索引<。此外，如果您显示X < Y和Y < X。这意味着这些问题具有相同的硬度。
在最后一点需要注意的是什么引述报告中称大约减少...减少是一种算法......。