Complexity of converting a boolean circuit to a boolean formula

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?

• what type of gates does the circuit have? – Lev Reyzin Feb 11 '11 at 20:24
• 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 Feb 11 '11 at 20:28
• 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 Feb 11 '11 at 20:28
• In general you would expect that any equivalent formula could be of exponential size even for a small circuit. – Kristoffer Arnsfelt Hansen Feb 11 '11 at 21:46
• 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 Feb 11 '11 at 22:11

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.
• @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 Feb 12 '11 at 3:29