3CNF SAT

概念：- 在 3CNF SAT 中，您至少有 3 个子句，在子句中，您将拥有几乎 3 个文字或常量

例如 (X+Y+Z) (X+Y+Z) (X+Y+Z)
您可以定义为 (XvYvZ) ᶺ (XvYvZ) ᶺ (XvYvZ)
V=OR 运算符
^ =AND 运算符

这些都是在 3CNF SAT 中需要考虑的要点。

证明：-

1. 3CNF SAT 的概念
2. SAT≤ρ 3CNF SAT
3. 3CNF≤ρ SAT
4. 3CNF ϵ NPC

1. 概念：- 在 3CNF SAT 中，您至少有 3 个子句，在子句中，您将拥有几乎 3 个文字或常量。
2. SAT ≤ρ 3CNF SAT：- 在其中，首先您需要将 SAT 中创建的布尔函数转换为 3CNF，无论是 POS 形式还是 SOP 形式，都在多项式时间内
        F=X+YZ
           = (X+Y) (X+Z)
          = (X+Y+ZZ') (X+YY'+Z)
          = (X+Y+Z) (X+Y+Z') (X+Y+Z) (X+Y'+Z)
          = (X+Y+Z) (X+Y+Z') (X+Y'+Z)
3. 3CNF ≤p SAT： - 通过具有三个文字的布尔函数，我们可以将整个函数简化为一个较短的函数。
        F= (X+Y+Z) (X+Y+Z') (X+Y'+Z)
          = (X+Y+Z) (X+Y+Z') (X+Y+Z) (X+Y'+Z)
          = (X+Y+ZZ') (X+YY'+Z)
          = (X+Y) (X+Z)
          = X+YZ
4. 3CNF ϵ NPC： - 众所周知，您可以通过 SAT 获取 3CNF，并通过 CIRCUIT SAT 获取 SAT，而 CIRCUIT SAT 来自 NP。

NPC 的证明：-

1. 这表明您可以轻松地将 SAT 的布尔函数转换为 3CNF SAT，并在多项式时间内通过归约概念满足 3CNF SAT 的概念。
2. 如果您想验证 3CNF SAT 中的输出，请执行归约并转换为 SAT 和 CIRCUIT，以检查输出

如果您能实现这两点，则意味着 3CNF SAT 也在 NPC 中