<p>If I understand your question correctly, I'd say you could use the standard reduction from CIRCUIT-SAT to SAT: Represent each gate as a new variable, and then represent the entire circuit in CNF form, with each clause having the form $(v\leftrightarrow\phi)$, where $v$ is the new variable, and the formula for the gate is given by $\phi$, using the variables for other gates to represent the inputs. This can be done by a simple traversal (in linear time, which is clearly optimal).</p>

<p>For example, if you hade three inputs, $x_1$, $x_2$, and $x_3$, with AND gates linking $x_1$ and $x_2$ as well as $x_2$ and $x_3$, and an OR gate linking their outputs, you could introduce three variables to represent the gates—$v_1$, $v_2$, and $v_3$, respectively—and rewrite the formula to $$(v_1\leftrightarrow(x_1\land x_2))\land (v_2\leftrightarrow(x_2\land x_3))\land (v_3\leftrightarrow(v_1\lor v_2))\land v_3\,.$$ Note that the output variable is included explicitly.</p>

<p><em>Introduction to Algorithms</em> by Cormen et al. explains this in detail, in the chapter on NP-Completeness.</p>

CC BY-SA 3.0
2013-11-01T21:49:03.107Z
is this the same as the [tseitin transformation](http://en.wikipedia.org/wiki/Tseitin-Transformation)?
vzn
CC BY-SA 2.5
2011-02-11T20:54:59.250Z
Doesn't CIRCUIT-SAT use fan-out 1 gates?
Mark Reitblatt
CC BY-SA 2.5
2011-02-11T21:08:22.487Z
Sure—but as far as I can see, that doesn't affect the reduction/transform. The idea of representing each output as a new variable means that you can reuse each output as an input several times (corresponding to arbitrarily large fan-out). In other words, the solution given in this answer should work for arbitrary circuits.
Magnus Lie Hetland
CC BY-SA 2.5
2011-02-11T21:15:56.457Z
Yup, that seems right. Cool.
Mark Reitblatt
CC BY-SA 2.5
2011-02-11T21:42:59.707Z
My guess would be that this is *not* what is being asked for. I think what is wanted is to make a formula on the same set of variables as the circuit.
Kristoffer Arnsfelt Hansen
CC BY-SA 2.5
2011-02-11T21:54:10.883Z
Hm. Yes, you're probably right. Introducing the new variables make sense in the CIRCUIT-SAT to CNF-SAT case, but not in a more general setting—I agree.
Magnus Lie Hetland
CC BY-SA 2.5
2011-02-11T22:03:10.610Z
Let see what the asker responds.
Kristoffer Arnsfelt Hansen
CC BY-SA 2.5
2011-02-12T03:29:49.277Z
@Kristoffer: I meant exactly what you said. Given a circuit $C$ on $x_1, x_2, \ldots, x_n$ I want the formula $\phi(x_1, x_2, \ldots, x_n)$ to be the exact boolean expression for the circuit.
Nikhil
CC BY-SA 2.5
2011-02-11T20:32:08.287Z
2011-02-11T20:54:30.373Z
2011-02-11T20:54:30.373Z
Magnus Lie Hetland
<p>Given a boolean circuit $C$ on $n$ variables (which uses just NOT,AND and OR gates), what is the most efficient way to extract the boolean formula represented by the circuit? Is there a polytime algorithm for this problem?</p>

CC BY-SA 2.5
2011-02-11T20:24:16.870Z
what type of gates does the circuit have?
Lev Reyzin
CC BY-SA 2.5
2011-02-11T20:28:49.197Z
What restrictions on fan-in or fan-out? If it's just single fan-out then it's trivial: the circuit itself is essentially an AST for the formula.
Mark Reitblatt
CC BY-SA 2.5
2011-02-11T20:28:55.860Z
Bounded fan-in to be general. But to be precise, lets say the AND and OR have fan-in 2. In many references in the literature, I find that a circuit and formulas are used interchangeably, but I want to know if converting a circuit to a formula is an easy problem.
Nikhil
CC BY-SA 2.5
2011-02-11T20:34:43.510Z
@Mark: Can you elaborate/give me a reference? Also I'd be interested in the case when the gates have fan-out > 1
Nikhil
CC BY-SA 2.5
2011-02-11T20:43:04.167Z
Each gate could then only be the "child" of one other gate, so just use each node directly as an operator in your formula, placing the subformula for the child nodes/gates in parentheses, if needed. (Basically, what Mark said.) For fa-out > 1, see my answer, below.
Magnus Lie Hetland
CC BY-SA 2.5
2011-02-11T21:46:31.717Z
In general you would expect that any equivalent formula could be of exponential size even for a small circuit.
Kristoffer Arnsfelt Hansen
CC BY-SA 2.5
2011-02-11T22:11:19.950Z
*Polynomial size formulas* are equivalent to $NC^1$ *circuits*. *Polysize circuits* ($P/poly$) are not know to be equivalent to $NC^1$. The formulas and circuits are used in interchangeably usually when the depth of the circuit is bounded.
Kaveh
CC BY-SA 2.5
2011-02-12T03:36:26.113Z
@Kristoffer: Yeah, intuitively I feel the same way, but can you give a lower bound?
Nikhil
<cc.complexity-theory><time-complexity><boolean-functions>
Complexity of converting a boolean circuit to a boolean formula
Nikhil
# Complexity of converting a boolean circuit to a boolean formula

(Asked by: username_0 on 2011-02-11)

Given a boolean circuit $C$ on $n$ variables (which uses just NOT,AND and OR gates), what is the most efficient way to extract the boolean formula represented by the circuit? Is there a polytime algorithm for this problem?

**Tags:** cc.complexity-theory, time-complexity, boolean-functions
> **Comments:**
> **username_1**: what type of gates does the circuit have?  
> **username_2**: What restrictions on fan-in or fan-out? If it's just single fan-out then it's trivial: the circuit itself is essentially an AST for the formula.  
> **username_0**: Bounded fan-in to be general. But to be precise, lets say the AND and OR have fan-in 2. In many references in the literature, I find that a circuit and formulas are used interchangeably, but I want to know if converting a circuit to a formula is an easy problem.  
> **username_0**: @Mark: Can you elaborate/give me a reference? Also I'd be interested in the case when the gates have fan-out > 1  
> **username_3**: Each gate could then only be the "child" of one other gate, so just use each node directly as an operator in your formula, placing the subformula for the child nodes/gates in parentheses, if needed. (Basically, what Mark said.) For fa-out > 1, see my answer, below.  
> **username_4**: In general you would expect that any equivalent formula could be of exponential size even for a small circuit.  
> **username_5**: *Polynomial size formulas* are equivalent to $NC^1$ *circuits*. *Polysize circuits* ($P/poly$) are not know to be equivalent to $NC^1$. The formulas and circuits are used in interchangeably usually when the depth of the circuit is bounded.  
> **username_0**: @Kristoffer: Yeah, intuitively I feel the same way, but can you give a lower bound?  

---

## 1 answers

### Answer by username_3 on 2011-02-11. Score: 8

If I understand your question correctly, I'd say you could use the standard reduction from CIRCUIT-SAT to SAT: Represent each gate as a new variable, and then represent the entire circuit in CNF form, with each clause having the form $(v\leftrightarrow\phi)$, where $v$ is the new variable, and the formula for the gate is given by $\phi$, using the variables for other gates to represent the inputs. This can be done by a simple traversal (in linear time, which is clearly optimal).

For example, if you hade three inputs, $x\_1$, $x\_2$, and $x\_3$, with AND gates linking $x\_1$ and $x\_2$ as well as $x\_2$ and $x\_3$, and an OR gate linking their outputs, you could introduce three variables to represent the gates—$v\_1$, $v\_2$, and $v\_3$, respectively—and rewrite the formula to $$(v\_1\leftrightarrow(x\_1\land x\_2))\land (v\_2\leftrightarrow(x\_2\land x\_3))\land (v\_3\leftrightarrow(v\_1\lor v\_2))\land v\_3\,.$$ Note that the output variable is included explicitly.

*Introduction to Algorithms* by Cormen et al. explains this in detail, in the chapter on NP-Completeness.

> **Comments:**
> **username_2**: Doesn't CIRCUIT-SAT use fan-out 1 gates?  
> **username_3**: Sure—but as far as I can see, that doesn't affect the reduction/transform. The idea of representing each output as a new variable means that you can reuse each output as an input several times (corresponding to arbitrarily large fan-out). In other words, the solution given in this answer should work for arbitrary circuits.  
> **username_2**: Yup, that seems right. Cool.  
> **username_4**: My guess would be that this is *not* what is being asked for. I think what is wanted is to make a formula on the same set of variables as the circuit.  
> **username_3**: Hm. Yes, you're probably right. Introducing the new variables make sense in the CIRCUIT-SAT to CNF-SAT case, but not in a more general setting—I agree.  
> **username_4**: Let see what the asker responds.  
> **username_0**: @Kristoffer: I meant exactly what you said. Given a circuit $C$ on $x_1, x_2, \ldots, x_n$ I want the formula $\phi(x_1, x_2, \ldots, x_n)$ to be the exact boolean expression for the circuit.  
> **username_6**: is this the same as the [tseitin transformation](http://en.wikipedia.org/wiki/Tseitin-Transformation)?  

---

