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

  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Apr 5 '20 at 11:46
  • $\begingroup$ It would make more sense to allow parallel edges. This is in line with the equivalence to straight-line programs. $\endgroup$ – Yuval Filmus Apr 5 '20 at 11:47

Your Answer

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

Browse other questions tagged or ask your own question.