4
$\begingroup$

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?

$\endgroup$

1 Answer 1

3
$\begingroup$

It's not necessarily the case that each input gate is on a path to the output gate. Determining if there is a path in a directed (acyclic) graph from one node s to another node t is NLOGSPACE-complete, so it is not a condition that you can arbitrarily enforce on (say) LOGSPACE-uniform circuits. It is easy to enforce this condition without loss of generality on P-uniform circuits: if you only require that the circuit be constructed in polynomial time, then after building the circuit it is easy to compute the strongly connected components of the graph representing the circuit, and throw out all gates that do not have a path to the output gate. Hence the inputs that do not eventually connect to the output would simply not be present. (Note I am not sure if this is precisely what you want.)

Still, I can't think of any typical usages of circuits where some input gates may not have a path to the output. Most reductions involving circuits are from machines to circuits, and we typically assume that a machine reads all its input bits. And when one is trying to prove a circuit lower bound, one always considers functions that depend on every bit.

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?

$\endgroup$
6
  • $\begingroup$ Boolean circuit is an acyclic graph, are you sure that accessibility problem for acyclic graphs is still $NLOGSPACE$-complete? $\endgroup$ Commented May 20, 2010 at 21:29
  • $\begingroup$ I'm looking for a sub LOGSPACE upperbound for a DLOGTIME-uniform family. Algorithms for arbitrary circuits keep hitting (as you mention) s t connectivity or needing transitive closure. I was hopping that I could assume every input gate was on a path to the output to bypass around this problem. $\endgroup$ Commented May 20, 2010 at 21:44
  • 3
    $\begingroup$ @Grigory Yes its still NL-complete, you can (in at least logspace) convert a cyclic graph to a leveled acyclic graph (the construction is very similar to the one on page 333 of Sipser's Textbook (2nd edition)). $\endgroup$ Commented May 20, 2010 at 21:50
  • $\begingroup$ @Niall: That sounds like a annoying problem to have. There is a kind of dumb way to enforce the condition that may help you, which I will describe in an update to my answer. $\endgroup$ Commented May 20, 2010 at 22:16
  • $\begingroup$ @Niall: Did you have any further comments on my answer to your question? $\endgroup$ Commented May 24, 2010 at 9:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .