2
$\begingroup$

Edit: Here's maybe a clearer presentation of my question. In a Boolean formula, all the gates have fan-out 1, and the graph representing the formula is a tree. In a Boolean circuit, the gates can have multiple outputs. What can be said about formula size as compared to circuit size?

I am learning some basics about classical circuit complexity, and have a confusion centering around the role of fan-out.

In various references (e.g. the textbook by Vollmer), circuit size is defined with respect to a basis where each gate has fan-out 1, like say AND, OR and NOT. A natural, simple operation seems to me to be fan-out, where I just copy a bit so it can be used twice in the circuit.

I am wondering how allowing fan-out changes the size of a minimal circuit computing a Boolean function.

A naive observation is that if I have a circuit of depth d that uses fan-out (say with two outputs), I could replace it with a circuit without fan-out while increasing the circuit size by at most $2^d$ (make a copy of the circuit below each fan-out, to compute that bit twice). Unless $d$ is $O(\log n)$ for $n$ the input size, this changes a polynomial size circuit to a super-polynomial one, so at least using this observation alone fan-out seems to have a notable effect on circuit size.

Is there a better way to remove fan-out gates than the above? Or is there a motivation for focusing on notions of circuit size / complexity that exclude fan-out?

$\endgroup$
1
  • $\begingroup$ What, formally and for above question, is a gate? What are gates in a Boolean formula, formula size, circuit size, fan-out? I remember fan-out of a gate as the number of "standard" inputs it is able to drive (within specs). $\endgroup$
    – greybeard
    Aug 17 at 12:59
1
$\begingroup$

Restricting fan-out is crucial in reversible computing, in which duplicating values is impossible. This is related to quantum computing.

Another circuit model without fan-out which has been studied recently is comparator circuits, see for example Mayr and Subramanian, The complexity of circuit value and network stability or the more recent The complexity of the comparator circuit value problem. Comparator circuits are not expected to be P-complete, and in particular, are expected to be weaker than circuits which do allow fan-out. See Comparator Circuits over Finite Bounded Posets for what happens when we allow the wires to carry values from different posets (rather than the Boolean lattice $\{0,1\}$).

$\endgroup$

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.