Question

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 TC⁰ which is a non-uniform constant-depth circuit, and let k_n be the circuit instance at input size n, does that mean that the following sentence is allowed or not: depth(k_i) ≠ depth(k_j) 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 ?

Answer 1

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.