电路SAT可满足性

根据给定的基于决策的NP问题, 你可以设计电路并在P时间内验证给定的输出。电路如下：-

注意：-你可以设计电路并在多项式时间内验证上述输出, 但请记住, 你永远无法在多项式时间内根据输入/高输入组预测产生高输出的门数。因此, 你验证了生成和转换已在多项式时间内完成。所以你在NPC中。

SAT（满意度）：-

如果输入的给定值的输出为true / high / 1, 则布尔函数被称为SAT。

F = X + YZ（通过CIRCUIT SAT创建布尔函数）

这些点, 你必须为NPC执行

1. SAT概念
2. 电路SAT≤ρSAT
3. SAT≤ρ电路SAT
4. SAT ϵ NPC

1. 概念：-如果输入的给定值的输出为true / high / 1, 则布尔函数被称为SAT。
2. CIRCUITSAT≤ρSAT：-在此转换中, 你必须像我们所做的那样在多项式时间内将CIRCUIT SAT转换为SAT
3. SAT≤ρCIRCUIT SAT：-为了验证输出, 你必须在多项式时间内将SAT转换为CIRCUIT SAT, 并且通过CIRCUIT SAT, 你可以成功获得输出的验证
4. SAT ϵ NPC：-众所周知, 你可以通过NP的CIRCUIT SAT获得SAT。

NPC的证明：-在从SAT到SAT的多项式时间内已成功地进行了约简。就像在上面的对话中一样, 在多项式时间内也已验证了输出。

如此得出结论SAT NPC。