principleMinor
Formulas vs Circuits
Viewed 0 times
circuitsformulasstackoverflow
Problem
In boolean circuit complexity, a circuit is just defined by a Directed Acyclic Graphs with designated input and output nodes, where the intermediate nodes compute a specific boolean function. A circuit is called a formula if the underlying graph is a tree. i.e., the fan-out of each node is $1$. Is it true that for a formula, (given that its fan-out is already $1$, by defintion) the fan-in is also constant?
In the usual definition of formulas, this is never spelt out(Its always defined as a circuit where all gates have fan-out $1$). But somehow I seem to carry around this intuitively that formulas are always bounded fan-in. (It might be partly due to the fact that poly-sized boolean formulas correspond to $\mathsf{NC^1}$ which is a complexity class defined by bounded fan-in circuits of logarithmic depth).
So my question is, if you bound the fan-out of the circuit to be $1$, does it imply even the fan-in should be constant for every gate? I tried to use a counting argument, that says that the indegree and outdegree of the graphs must sum to the same, but somehow a water tight proof eludes me. First of all, is my intuition correct?
In the usual definition of formulas, this is never spelt out(Its always defined as a circuit where all gates have fan-out $1$). But somehow I seem to carry around this intuitively that formulas are always bounded fan-in. (It might be partly due to the fact that poly-sized boolean formulas correspond to $\mathsf{NC^1}$ which is a complexity class defined by bounded fan-in circuits of logarithmic depth).
So my question is, if you bound the fan-out of the circuit to be $1$, does it imply even the fan-in should be constant for every gate? I tried to use a counting argument, that says that the indegree and outdegree of the graphs must sum to the same, but somehow a water tight proof eludes me. First of all, is my intuition correct?
Solution
No. Take for example $\mathsf{AC^0}$. It is polynomial-size bounded-depth circuits. Being DAG or tree doesn't change the class. The fan-in can be arbitrarily large.
If the fan-in is bounded we end-up with $\mathsf{NC^0}$ which is much weaker. It cannot compute any function where the output depends on more than a bounded number of inputs as each gate with at least two inputs will decrease the number of usable wires by one and there is no way of increasing them.
Note also that the number of gates (ignoring single input gates like negation) in any circuit with $n$ inputs and with fan-out $1$ is going to be at most $n-1$.
If the fan-in is bounded we end-up with $\mathsf{NC^0}$ which is much weaker. It cannot compute any function where the output depends on more than a bounded number of inputs as each gate with at least two inputs will decrease the number of usable wires by one and there is no way of increasing them.
Note also that the number of gates (ignoring single input gates like negation) in any circuit with $n$ inputs and with fan-out $1$ is going to be at most $n-1$.
Context
StackExchange Computer Science Q#9940, answer score: 7
Revisions (0)
No revisions yet.