4

我从这里（第 8、9 页）阅读了关于 NP 硬度的信息，在注释中，作者将 3-SAT 形式的问题简化为可用于解决最大独立集问题的图形。

在示例中，作者将以下 3-SAT 问题转换为图。3-SAT问题是：

(a ∨ b ∨ c) ∧ (b ∨ ~c ∨ ~d) ∧ (~a ∨ c ∨ d) ∧ (a ∨ ~b ∨ ~d)

生成的等效图是：

图形

作者指出，两个节点通过一条边连接，如果：

  1. 它们对应于同一子句中的文字
  2. 它们对应于一个变量及其倒数。

我很难理解作者是如何提出这些规则的。

  • 为什么我们需要在变量和它的逆变量之间画边？
  • 假设有两个子句，子句 1 有 (a,b,~c)，子句 2 有 (~a,b,c) 来连接子句 1 和子句 2，为什么我们必须连接 a 和 ~a？为什么我们不能将 a (clause 1) 与 c (clause 2) 连接起来呢？
4

1 回答 1

6

我认为可以解决问题的是减少概念。假设你对一个问题很熟悉，比如 X(ie 3-SAT)[是什么意思？你知道 X 有多难解决]。此外，您目前正在分析另一个新问题，例如 Y（即独立集）......

你对 X 的了解如何帮助你想出 Y？如果你能找到它们之间的关系（即归约），那么你可以使用关于 X 到 Y 的知识。诸如"Y is hard than X"或"Y is as hard as X" 之类的东西。所以这个解决方案想要做的是找到两个问题之间的关系。

在可计算性理论和计算复杂性理论中，约简是一种将一个问题转化为另一个问题的算法。从一个问题到另一个问题的简化可以用来表明第二个问题至少和第一个问题一样困难。

您在此处提到的两条规则就是全部（即关系）。

  1. 您不能同时选择边的两个顶点。此外，您不能同时设置变量及其否定 TRUE。
  2. 您必须在子句中有一个 TRUE 变量。此外，为了最大化所选顶点的数量，您必须从每个子句中选择一个节点。

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

PS：这里提到的作为解决 3-SAT 到独立集问题的证据并不精确。这个解释只是为了让您更深入地了解证明想要执行的程序。证明留给学术笔记。

减少的另一件重要的事情是它自己的时间。另一方面，缩减时间（即，将 X 实例转换为 Y 实例所需的时间）必须小于 X 问题时间（它支配了 X 求解时间）。

还有一些符号表明，X < Y以其他时间顺序作为 的索引<。此外，如果你显示X < Y和Y < X. 这意味着这些问题具有相同的难度。

最后一点请注意，引用的注释所说的关于归约……归约是一种算法……。

于 2017-12-05T17:08:05.400 回答