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

Non-uniform circuits, according to my understanding, are those which have different circuit depending on the input size. Constant depth circuit are those whose depth is constant in the input size. So if for example we considered an instance k of the complexity class TC0 which is a non-uniform constant-depth circuit, and let kn be the circuit instance at input size n, does that mean that the following sentence is allowed or not: depth(ki) ≠ depth(kj) when i≠j.

In other words, does the non-uniformity of a complexity class allow a constant-depth circuit to have different depths for different input size or not ?

share|cite|improve this question
up vote 7 down vote accepted

Recall "non-uniform circuits" are represented as an infinite sequence {$C_n$}, where $C_n$ is the circuit that will handle $n$-bit inputs. The usual definition of "constant depth" means that the depth may vary from circuit $C_n$ to circuit $C_{n'}$, but the depth of $C_n$ is never larger than a fixed number $d$. That is, the maximum depth of any circuit in the family is a constant, independent of the input size to a circuit.

share|cite|improve this answer

Your Answer


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.