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个子句中, 你将有几乎3个文字或常量。
2. SAT≤ρ3CNF SAT：-首先, 你需要在多项式时间内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≤pSAT：-从具有三个文字的布尔函数中, 我们可以将整个函数简化为较短的一个。 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, 并且可以通过来自NP的CIRCUIT SAT获得SAT。

NPC证明：

1. 它表明你可以轻松地将SAT的布尔函数转换为3CNF SAT, 并且还可以在多项式时间内通过归约概念满足3CNF SAT的概念。
2. 如果要验证3CNF SAT中的输出, 请执行精简并将其转换为SAT和CIRCUIT来检查输出

如果你能达到这两点, 则意味着NPC中也有3CNF SAT