28.13. Reduction of Circuit SAT to SAT¶
28.13.1. Reduction of Circuit SAT to SAT¶
The following slideshow shows that an instance of the Circuit Satisfiability problem can be reduced to an equivalent instance of the SAT problem in polynomial time.
1 / 40
Settings
Reduction of Circuit SAT to SAT
$(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)$
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.
<<<>>>
Reduction of Circuit SAT to SAT
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.
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
'If and only if' (denoted by $\leftrightarrow$) is a boolean operator that follows the following truth table.
Let C = A $\leftrightarrow$ B
- A
- B
- C
- T
- T
- T
- T
- F
- F
- F
- T
- F
- F
- F
- T
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.
Check each line of the truth table to convince yourself that this is true.
We will also use the following laws of boolean logic.
Distributive Law
$A\cdot (B + C) = A\cdot B + A\cdot C$
$ A + B\cdot C = (A+B)\cdot (A+C)$
DeMorgan's Law
$ \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$
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.
A NOT gate can be reduced to a CNF formula in polynomial time
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.
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.
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.
An AND gate with any number of input wires can be reduced to a similar CNF formula
in polynomial time.
in polynomial time.
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.
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.
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.
An OR gate with any number of input wires can be reduced to a similar CNF formula
in polynomial time
in polynomial time
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$.
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
$x_{10}$
$\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)$)
=
$x_{10}$
$\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)$
Note: This CNF expression can be constructed in polynomial time.
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.
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.
This reduction can help in providing an NP Completeness proof for SAT.