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
。这意味着这些问题具有相同的难度。
最后一点请注意,引用的注释所说的关于减少...减少是一种算法....