# Is every input gate of a Boolean Circuit (to decide a language) on a path to the output gate?

In complexity theory, when a uniform family of circuits recognises a language is it the case that each of the input gates is on a path to the output gate?

That is, there are no input gates with wires connected to gates that do not eventually connect to the output gate.

The definitions found in the literature are general enough for sections of the circuit to not connect to the output gate. However, it seems to me that without assuming that all input gates have a path to the output graph some things, for example reductions, get needlessly tricky.

Has anyone seen this mentioned before? Is it a well known assumption?

-

UPDATE: Here's a silly way to enforce the condition you want, but I don't know if it will help you in your particular case. Suppose for simplicity that the number of inputs $n$ is a power of $2$. Make a complete binary tree of $2n-1$ new gates (where all edges lead towards the root of the tree), so we have $n$ leaves. Label all nodes in the tree as $AND$ gates. For the $i$th leaf in the tree, lead in the inputs $x_i$ and $\neg x_i$. Now $OR$ the root of this binary tree with the output gate of your original circuit, and make this $OR$ your new output gate. Clearly every input now has a path to an output gate and the functionality of the circuit has not changed. Moreover this transformation is extremely uniform; I am pretty sure it can be made DLOGTIME-uniform. But is this really what you need for your problem?
Boolean circuit is an acyclic graph, are you sure that accessibility problem for acyclic graphs is still $NLOGSPACE$-complete? – Grigory Yaroslavtsev May 20 '10 at 21:29