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. 它们对应于同一子句中的文字
  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.

你在这里提到的两条规则就是所有这些(即关系)。

  1. 您不能同时 select 一条边的两个顶点。此外,您不能同时设置变量及其否定 TRUE。
  2. 您必须在子句中有一个 TRUE 变量。此外,为了最大化 selected 顶点的数量,您必须 select 每个子句形成一个节点。

这显示了这些规则的来源。

PS:这里注意的是不精确作为解决3-SAT独立集问题的证明.这个解释只是为了让你更深入地了解证明想要做什么程序。证明留给学术笔记。

减少的另一个重要因素是它自己的时间。另一方面,减少时间(即将 X 实例转换为 Y 实例所需的时间)必须小于 X 问题时间(o.w 它支配 X 解决方案时间)。

也有一些符号表示X < Y和另一个时间顺序作为<的索引。此外,如果您显示 X < YY < X。这意味着这些问题具有相同的难度。

最后一点请注意,引用的注释所说的关于减少...减少是一种算法....