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

Context: googling existing results on Circuit Complexity.

I'm aware there are classes like AC, ACC, TC, NC, etc..

Now, suppose I have a circuit, it has the following additional program:

The circuit is divided into layers. Layer i+1 is only allowed inputs from layer i. It is not allowed inputs from layer i-1, or layer i-2, ...

What is the proper term for this restriction?


share|improve this question
try the original stackoverflow –  Will Jagy Oct 4 '11 at 22:46
Or rather, cstheory.stackexchange.com –  Niel de Beaudrap Oct 4 '11 at 22:49
I don't think this is off topic here, but it will certainly get better answers at cstheory.stackexchange.com –  David Speyer Oct 4 '11 at 23:10
In the case of straight line programs, this property is simply referred as the SLP being "layered". For circuits, I am not aware of any proper term. Note that this is not a real restriction since any circuit can be layered using a few new gates. –  Bruno Oct 4 '11 at 23:12
For circuits it's also called layered. –  Emil Jeřábek Oct 5 '11 at 1:23

Your Answer


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

Browse other questions tagged or ask your own question.