电路SAT可满足性电路SAT可满足性|算法设计与分

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

文章图片
注意：-你可以设计电路并在多项式时间内验证上述输出, 但请记住, 你永远无法在多项式时间内根据输入/高输入组预测产生高输出的门数。因此, 你验证了生成和转换已在多项式时间内完成。所以你在NPC中。 SAT（满意度）：- 如果输入的给定值的输出为true / high / 1, 则布尔函数被称为SAT。
【电路SAT可满足性】F = X + YZ（通过CIRCUIT SAT创建布尔函数）
这些点, 你必须为NPC执行

SAT概念
电路SAT≤ρSAT
SAT≤ρ电路SAT
SAT ? NPC

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

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