# Boolean circuit multigraph

Let us say that our definition of a circuit is the one of a boolean circuit from [Vollmer]. He uses directed acyclic graphs to represent circuits where the computation nodes are labeled with some functions which come from a set of possible operations (called basis).

Let us say that we only allow the operation $$\land$$ for our circuit (i.e. the basis only consists of $$\land$$). Is $$x \land x$$ a circuit if $$x$$ denotes an input gate? I don't think so, because the input gate $$x$$ is only allowed to occure once in the graph and then we would need two edges to the $$\land$$-node, i.e. we would need a multigraph. A way around would be to force a basis to have an identity operation. For instance using the basis $$\land, id$$ we could of course build the $$x \land x$$ circuit (this is also the case if we can build the identity operation in any other way, e.g. if we have $$\neg$$ in our basis) even though we have to increase the size of the circuit by using $$id$$. It seems very counterintuitive that such a simple circuit is in fact not a circuit over the basis $$\land$$, so is my reasoning correct?

[Vollmer] Heribert Vollmer, Introduction to Circuit Complexity

• It depends on the exact definition. However, let me say that this is an extremely fine and unimportant point. Gates of the form $x \land x$ aren't useful at all. Apr 5 '20 at 11:46
• It would make more sense to allow parallel edges. This is in line with the equivalence to straight-line programs. Apr 5 '20 at 11:47