10
$\begingroup$

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?

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

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.

$\endgroup$
  • $\begingroup$ Doesn't CIRCUIT-SAT use fan-out 1 gates? $\endgroup$ – Mark Reitblatt Feb 11 '11 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$ – Magnus Lie Hetland Feb 11 '11 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$ – Kristoffer Arnsfelt Hansen Feb 11 '11 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$ – Magnus Lie Hetland Feb 11 '11 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$ – Nikhil Feb 12 '11 at 3:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.