Circuit-SAT & SAT

Circuit-SAT

Circuit-SAT 是 所有 NPC 的基石，由它開始做 reduction，證明其他問題也是 NPC。

Circuit-SAT is NP-Complete, proof by Cook many years ago, we can use this as a cornerstone, to perform reduction to other problem, prove they are NP-Complete as well, like SAT. First we prove a problem is in NP, then we use reduction to prove it is in NP-hard, then conclude that it is in NP-Complete.

Circuit-SAT ${\le }_p$ SAT

For this circuit, the SAT formula $\varphi$ can be written as follow:

$\begin{array}{rl}\varphi =x_{10}& \wedge (x_4⟺\neg x_3)\\ & \wedge (x_5⟺x_1\vee x_2)\\ & \wedge (x_6⟺\neg x_4)\\ & \wedge (x_7⟺x_1\wedge x_2\wedge x_4)\\ & \wedge (x_8⟺x_5\vee x_6)\\ & \wedge (x_9⟺x_6\vee x_7)\\ & \wedge (x_{10}⟺x_7\wedge x_8\wedge x_9)\end{array}$

Each $()$ is a clause, its value is always true according to boolean logic. We can transform the circuit into $\varphi$ in polynomial time.

Circuit-SAT is satisfiable $⟺$ SAT is satisfiable

$(\Rightarrow )$: if circuit is satisfiable, means that the final output, in this case $x_{10}$ is true, and because all clause are always true, the SAT is satisfiable.

$(\Leftarrow )$: if SAT is satisfiable, which means that all clause and $x_{10}$ must all be true, and thus the circuit is satisfiable.

Links

• NP Completeness Definition

Reference

• Introduction to Algorithm
• Reduction of Circuit SAT to SAT