This slideshow presents how to reduce an input instance to the Circuit-SAT problem to an equivalent instance to the SAT problem in polynomial time.

We start by giving some background.

The reduction shown in this slideshow relies heavily on the following identity:

'If and only if' (denoted by $\leftrightarrow$) is a boolean operator that follows the following truth table.

Let C = A $\leftrightarrow$ B

A$\leftrightarrow$B is equivalent to $(\overline{A} + B)\cdot(A + \overline{B}) \cdots\cdots$ Identity 1.

Check each line of the truth table to convince yourself that this is true.

We will also use the following laws of boolean logic.

$A\cdot (B + C) = A\cdot B + A\cdot C$

$A + B\cdot C = (A+B)\cdot (A+C)$

$\overline{A \cdot B} = \overline{A} + \overline{B}$

$\overline{A + B} = \overline{A}\cdot\overline{B}$

Our reduction takes the following steps:

1. Assign a variable $x_i$ for each input signal of a circuit.

2. Assign a variable (say $x_o$) for each output wire of a gate.

3. Set up an 'if and only if' formula for each gate.
    (Recall from an earlier slide: 'If and only if' can be expressed as a conjuntion of clauses.)
    Let ${\phi}_k$ be the formula for the $k$^th gate.

4. Let $x_O$ be the final output wire of the circuit.

    The CNF formula is $x_{o,f} \cdot {\phi}_1 \cdot {\phi}_2 \cdots$

x1

x2

The reduced CNF formula: $\phi$ = ($x_2 \leftrightarrow\overline{x_1}$)

= $(\overline{x_2} + \overline{x_1})\cdot(x_2 + \overline{\overline{x_1}})$ [Using Identity 1 (refer to slide 2)]

= $(\overline{x_1} + \overline{x_2})\cdot(x_1 + x_2)$ which is a conjunction of clauses.

Note: Since $x_2$ is the output of NOT on $x_1$, $(x_2 \leftrightarrow \overline{x_1})$ (i.e. $\phi$) is always True.

x1

x2

x3

The reduced CNF formula $\phi$ = ($x_3 \leftrightarrow$$x_1 \cdot x_2$)

= $( x_3 + \overline{x_1 \cdot x_2} )\cdot(\overline{x_3} + x_1 \cdot x_2)$   [Using Identity 1]

= $(x_3 + \overline{x_1} + \overline{x_2})\cdot(\overline{x_3} + x_1 \cdot x_2)$   [Using De Morgan's Law]

= $(\overline{x_1} + \overline{x_2} + x_3 )\cdot(\overline{x_3} + x_1)\cdot(\overline{x_3} + x_2)$   [Using Distributive Law]

    which is a conjunction of clauses.

Note:   Since $x_3$ is the output of AND on $x_1$ and $x_2$, $(x_3 \leftrightarrow x_1\cdot x_2)$ (i.e. $\phi$) is always True.

x1

x2

x3

x4

The reduced CNF formula $\phi$ = ($x_4 \leftrightarrow$$x_1 \cdot x_2 \cdot x_3$)

= $(x_4 + \overline{x_1\cdot x_2\cdot x_3})\cdot(\overline{x_4}+x_1\cdot x_2\cdot x_3)$   [Using Identity 1]

= $(x_4 + \overline{x_1} + \overline{x_2}+ \overline{x_3})\cdot(\overline{x_4}+x_1\cdot x_2\cdot x_3)$   [Using De Morgan's Law]

= $(x_4 + \overline{x_1} + \overline{x_2}+ \overline{x_3})\cdot(\overline{x_4} + x_1)\cdot(\overline{x_4} + x_2)\cdot(\overline{x_4} +x_3)$ [Using Distributive Law]

    which is a conjunction of clauses.

Note:   Since $x_4$ is the output of AND on $x_1$ $x_2$ and $x_3$, $(x_4 \leftrightarrow x_1\cdot x_2\cdot x_3)$ (i.e. $\phi$) is always True.

x1

x2

x3

The reduced CNF formula $\phi$ = ($x_3 \leftrightarrow$$(x_1 + x_2)$)

= $(x_3 + (\overline{x_1+x_2}))\cdot(\overline{x_3}+(x_1+x_2))$   [Using Identity 1]

= $(x_3 + \overline{x_1}\cdot\overline{x_2})\cdot(\overline{x_3}+x_1+x_2)$   [Using De Morgan's Law]

= $(x_3 + \overline{x_1})\cdot(x_3 + \overline{x_2})\cdot(\overline{x_3} + x_1 + x_2)$   [Using Distributive Law]

    which is a conjunction of clauses.

Note:   Since $x_3$ is the output of OR on $x_1$ and $x_2$, $(x_4 \leftrightarrow (x_1+x_2))$ (i.e. $\phi$) is always True.

x1

x2

x3

x4

The reduced CNF formula $\phi$ = ($x_4 \leftrightarrow$$(x_1 + x_2 + x_3)$)

= $(x_4 + (\overline{x_1+x_2+x_3}))\cdot(\overline{x_4}+(x_1+x_2+x_3))$   [Using Identity 1]

= $(x_4 + \overline{x_1}\cdot\overline{x_2}\cdot\overline{x_3})\cdot(\overline{x_4}+x_1+x_2+x_3)$   [Using De Morgan's Law]

= $(x_4 + \overline{x_1})\cdot(x_4 + \overline{x_2})\cdot(x_4 +\overline{x_3})\cdot(\overline{x_4} + x_1 + x_2 + x_3)$ [Using Distributive Law]

    which is a conjunction of clauses.

Since $x_4$ is the output of OR on $x_1$ $x_2$ and $x_3$, $(x_4 \leftrightarrow (x_1+x_2+x_3))$ (i.e. $\phi$) is always True.

As we saw, each gate in the circuit (with $n$ gates) can be reduced to a CNF formula $\phi$ in polynomial time.

If $x_O$ is the variable corresponding to the final output of the circuit, and ${\phi}_k$ is the CNF formula for gate $k$,
the circuit can be reduced to the CNF formula :

$x_O\cdot {\phi}_1 \cdot {\phi}_2 \cdots {\phi}_n$.

x1

x2

x3

A

B

C

D

E

F

G

x4

x5

x6

x7

x8

x9

x10

This circuit can be reduced to

$\cdot$

($x_4 \leftrightarrow \overline{x_3}$)

$\cdot$

($x_5 \leftrightarrow (x_1 + x_2)$)

$\cdot$

($x_6 \leftrightarrow \overline{x_4}$)

$\cdot$

($x_7 \leftrightarrow (x_1.x_2.x_4)$)

$\cdot$

($x_8 \leftrightarrow (x_5+x_6)$)

$\cdot$

($x_9 \leftrightarrow (x_7+x_6)$)

$\cdot$

($x_{10} \leftrightarrow (x_7.x_8.x_9)$)

=

$\cdot$

$(\overline{x_3} + \overline{x_4})\cdot(x_3+x_4)$

$\cdot$

$(x_5 + \overline{x_1})\cdot(x_5 + \overline{x_2})\cdot(\overline{x_5} + x_1 + x_2)$

$\cdot$

$(\overline{x_4} + \overline{x_6})\cdot(x_4+x_6)$

$\cdot$

$(x_7 + \overline{x_1} + \overline{x_2}+ \overline{x_4})\cdot(\overline{x_7} + x_1)\cdot(\overline{x_7} + x_2)\cdot(\overline{x_7} +x_4)$

$\cdot$

$(x_8 + \overline{x_5})\cdot(x_8 + \overline{x_6})\cdot(\overline{x_8} + x_5 + x_6)$

$\cdot$

$(x_9 + \overline{x_7})\cdot(x_9 + \overline{x_6})\cdot(\overline{x_9} + x_7 + x_6)$

$\cdot$

$(x_{10} + \overline{x_7} + \overline{x_8}+ \overline{x_9})\cdot(\overline{x_{10}} + x_7)\cdot(\overline{x_{10}} + x_8)\cdot(\overline{x_{10}} +x_9)$

The reduced CNF formula for a circuit with $n$ gates is of the $x_{o,f} \cdot {\phi}_1 \cdot {\phi}_2 \cdots$ where $\phi_k$ is the CNF formula
corresponding to the $k^{th}$gate.

1. If the circuit is satisfiable

The gates in a circuit perform a well defined function causing the $\phi_k$ formulae to be aways True.
Since the circuit is satisfiable, its final output $X_O$ evaluates to True.
Hence with all clauses satisfied, the reduced CNF formula also evaluates to True.

The CNF formula is satisfiable.

2. If the CNF formula is satisfiable

For the CNF formula to be satisfiable, all the clauses must be True.
Hence all the 'if and only if' formulae of the form i$\phi_k$ will also need to be True.
This preserves the functionality of all corresponding gates in the circuit.
Also the output $X_O$ is True.

Hence the circuit is satisfiable.