3-SAT如何简化为Independent set？
How can 3-SAT be reduced to Independent set?
我正在阅读 here（第 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（第 1 条）与 c（第 2 条）连接起来？
我觉得可以解决问题的是reduction概念。假设你熟悉一个问题说 X(即 3-SAT)[熟悉是什么意思？你知道解决 X] 有多么困难。此外，您目前正在分析另一个新问题，例如 Y（即独立集）...
你对 X 的了解如何帮助你想出 Y？如果你能找到它们之间的关系（即减少），那么你可以使用关于 X 到 Y 的知识。像 "Y is harder than X" 或 "Y is as hard as X"。所以这个解决方案想要做的是找到两个问题之间的关系。
In computability theory and computational complexity theory, a reduction is an algorithm for transforming one problem into another problem. A reduction from one problem to another may be used to show that the second problem is at least as difficult as the first.
你在这里提到的两条规则就是所有这些（即关系）。
- 您不能同时 select 一条边的两个顶点。此外，您不能同时设置变量及其否定 TRUE。
- 您必须在子句中有一个 TRUE 变量。此外，为了最大化 selected 顶点的数量，您必须 select 每个子句形成一个节点。
这显示了这些规则的来源。
PS:这里注意的是不精确作为解决3-SAT独立集问题的证明.这个解释只是为了让你更深入地了解证明想要做什么程序。证明留给学术笔记。
减少的另一个重要因素是它自己的时间。另一方面，减少时间（即将 X 实例转换为 Y 实例所需的时间）必须小于 X 问题时间（o.w 它支配 X 解决方案时间）。
也有一些符号表示X < Y和另一个时间顺序作为<的索引。此外，如果您显示 X < Y 和 Y < X。这意味着这些问题具有相同的难度。
最后一点请注意，引用的注释所说的关于减少...减少是一种算法....
我正在阅读 here（第 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（第 1 条）与 c（第 2 条）连接起来？
我觉得可以解决问题的是reduction概念。假设你熟悉一个问题说 X(即 3-SAT)[熟悉是什么意思？你知道解决 X] 有多么困难。此外，您目前正在分析另一个新问题，例如 Y（即独立集）...
你对 X 的了解如何帮助你想出 Y？如果你能找到它们之间的关系（即减少），那么你可以使用关于 X 到 Y 的知识。像 "Y is harder than X" 或 "Y is as hard as X"。所以这个解决方案想要做的是找到两个问题之间的关系。
In computability theory and computational complexity theory, a reduction is an algorithm for transforming one problem into another problem. A reduction from one problem to another may be used to show that the second problem is at least as difficult as the first.
你在这里提到的两条规则就是所有这些（即关系）。
- 您不能同时 select 一条边的两个顶点。此外，您不能同时设置变量及其否定 TRUE。
- 您必须在子句中有一个 TRUE 变量。此外，为了最大化 selected 顶点的数量，您必须 select 每个子句形成一个节点。
这显示了这些规则的来源。
PS:这里注意的是不精确作为解决3-SAT独立集问题的证明.这个解释只是为了让你更深入地了解证明想要做什么程序。证明留给学术笔记。
减少的另一个重要因素是它自己的时间。另一方面，减少时间（即将 X 实例转换为 Y 实例所需的时间）必须小于 X 问题时间（o.w 它支配 X 解决方案时间）。
也有一些符号表示X < Y和另一个时间顺序作为<的索引。此外，如果您显示 X < Y 和 Y < X。这意味着这些问题具有相同的难度。
最后一点请注意，引用的注释所说的关于减少...减少是一种算法....