电路SAT可满足性

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

电路SAT

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

微信公众号
手机浏览(小程序)
0
分享到:
没有账号? 忘记密码?