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?
$\begingroup$
$\endgroup$
8
-
$\begingroup$ what type of gates does the circuit have? $\endgroup$– Lev Reyzin ♦Feb 11, 2011 at 20:24
-
1$\begingroup$ 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. $\endgroup$– Mark ReitblattFeb 11, 2011 at 20:28
-
1$\begingroup$ 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. $\endgroup$– NikhilFeb 11, 2011 at 20:28
-
8$\begingroup$ In general you would expect that any equivalent formula could be of exponential size even for a small circuit. $\endgroup$– Kristoffer Arnsfelt HansenFeb 11, 2011 at 21:46
-
4$\begingroup$ 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. $\endgroup$– KavehFeb 11, 2011 at 22:11
|
Show 3 more comments
1 Answer
$\begingroup$
$\endgroup$
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.
answered Feb 11, 2011 at 20:32
-
$\begingroup$ Doesn't CIRCUIT-SAT use fan-out 1 gates? $\endgroup$ Feb 11, 2011 at 20:54
-
1$\begingroup$ 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. $\endgroup$ Feb 11, 2011 at 21:08
-
3$\begingroup$ 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. $\endgroup$ Feb 11, 2011 at 21:42
-
1$\begingroup$ 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. $\endgroup$ Feb 11, 2011 at 21:54
-
1$\begingroup$ @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. $\endgroup$– NikhilFeb 12, 2011 at 3:29