Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 3 down vote accepted

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?

share|improve this answer
    
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
    
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. –  Niall Murphy May 20 '10 at 21:44
3  
@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)). –  Niall Murphy May 20 '10 at 21:50
    
@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. –  Ryan Williams May 20 '10 at 22:16
    
@Niall: Thank you –  Grigory Yaroslavtsev May 21 '10 at 5:59

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.