MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
try the original stackoverflow – Will Jagy Oct 4 '11 at 22:46
Or rather, – 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 – 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.