# Nonuniform circuit families - don't have to specify for arbitrarily large, but finite, input lengths?

This is a question about nonuniform circuit families that's kind of bothering me. Let $\lbrace C_n \rbrace$ be a family of circuits for a language $L$ such that for inputs $x$ of length $n$, $C_n(x) = L(x)$. This implies that $C_n$ has to answer correctly on all inputs of the form $0y$, where $|y| \leq n-1$, right? In that case, that implies that in specifying a circuit family $\lbrace C_n \rbrace$, you can leave out arbitrary long (but finite) sequences of circuits in this (infinitary) "description", and you wouldn't have lost any part of your description.

I'm sure this is not profound in the slightest, but it does seem strange to me - that for each $n$, the circuit $C_n$ subsumes all of the $C_k$ for $k < n$.

• It does not, a string of length $n$ starting with $0$ is different from a string of length $n-1$. Nov 22 '10 at 2:18

No, your implication is wrong. The string $\vec{0}y$ is different from $y$. For example, assume that your circuits output the first bit of their inputs. If the first letter of $y$ is $1$ then you would get $C_{|y|}(y) = 1$, but $C_n(\vec{0}y) = 0$.