MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

Thanks!

share|cite|improve this question
    
try the original stackoverflow – Will Jagy Oct 4 '11 at 22:46
3  
Or rather, cstheory.stackexchange.com – Niel de Beaudrap Oct 4 '11 at 22:49
2  
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
4  
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
2  
For circuits it's also called layered. – Emil Jeřábek Oct 5 '11 at 1:23

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.