2
$\begingroup$

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!

Improve this question
$\endgroup$
6
  • $\begingroup$ try the original stackoverflow $\endgroup$
    – Will Jagy
    Commented Oct 4, 2011 at 22:46
  • 3
    $\begingroup$ Or rather, cstheory.stackexchange.com $\endgroup$
    – Niel de Beaudrap
    Commented Oct 4, 2011 at 22:49
  • 2
    $\begingroup$ I don't think this is off topic here, but it will certainly get better answers at cstheory.stackexchange.com $\endgroup$
    – David E Speyer
    Commented Oct 4, 2011 at 23:10
  • 4
    $\begingroup$ 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. $\endgroup$
    – Bruno
    Commented Oct 4, 2011 at 23:12
  • 2
    $\begingroup$ For circuits it's also called layered. $\endgroup$
    – Emil Jeřábek
    Commented Oct 5, 2011 at 1:23

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .