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?
Asked
Active
Viewed 2,848 times
13
-
what type of gates does the circuit have? – Lev Reyzin Feb 11 '11 at 20:24
-
1What 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
-
1Bounded 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
-
@Mark: Can you elaborate/give me a reference? Also I'd be interested in the case when the gates have fan-out > 1 – Nikhil Feb 11 '11 at 20:34
-
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 Feb 11 '11 at 20:43
-
8In 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
-
4Polynomial 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
-
@Kristoffer: Yeah, intuitively I feel the same way, but can you give a lower bound? – Nikhil Feb 12 '11 at 03:36
1 Answers
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.
Magnus Lie Hetland
- 1,520
- 10
- 17
-
-
1Sure—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 Feb 11 '11 at 21:08
-
-
3My 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 Feb 11 '11 at 21:42
-
1Hm. 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 Feb 11 '11 at 21:54
-
-
1@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 03:29
-