电路 SAT

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

注意：- 您可以在多项式时间内设计一个电路并验证给定的输出，但请记住，您永远无法预测在多项式时间内产生高输出的门数与输入/高输入集的对应关系。因此，您在多项式时间内验证了生产和转换。因此您属于 NPC。

SAT (可满足性)：-

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

F=X+YZ (通过 CIRCUIT SAT 创建了一个布尔函数)

您必须为 NPC 执行这些要点

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

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

NPC 的证明： - 还原已在多项式时间内从 CIRCUIT SAT 成功完成到 SAT。输出也已在多项式时间内得到验证，正如您在上述对话中所做的那样。

因此，得出结论，SAT ϵ NPC。