A family of circuits $(C_{1}, C_{2}, \ldots)$ is uniform if some log space transducer $T$ outputs $\langle C_{n}\rangle$ where $T$'s input is $1^{n}$. (from http://en.wikipedia.org/wiki/Boolean_circuit#Uniform_Boolean_Circuits)

Can anyone exlain this? I know what boolean circuits are, so only explanation needed is what and transducer exactly are.


Uniformity definition means that there is a deterministic Turing machine running in logarithmic space $\mathsf{L}$ that generates the description of the $n$th circuit from the unary encoding of $n$.

To have a better idea of what this is talking about, assume that we have a Turing machine $M$ in $\mathsf{P}$. Then for every input size $n$ we can generate a circuit of size $poly(n)$ that compute $M$ on inputs of size $n$. So we obtain a family of circuits $\{C_n\}_{n \in\mathbb{N}}$. However these circuits are not arbitrary independent circuits but coming from a single machine $M$.

The definition is good for large classes like $\mathsf{P}$ but it doesn't work for small complexity classes. For those classes we use deterministic logarithmic time $\mathsf{DLogTime}$ in place of $\mathsf{L}$. In place of printing the whole circuit we just require it to compute any given bit of the description of the $n$th circuit in logarithmic time.


A transducer is a finite state automata that (in effect) has both an input tape and an output tape. So instead of the normal DFA/NFA computation where the automaton has an input that it recognises (or equivalently, no input at all, and an output that it generates), a transducer reads from the input and writes to the output. Otherwise the definition is in essence a DFA/NFA.

So in this case the transducer takes a number (in the form of a string of $1$s - so $4$ would be $1111$) and produces the encoding of the circuit $C_{n}$ ($\langle X \rangle$ means the encoding of $X$ under some [sensible] encoding scheme). So even though the family of circuits is infinite, they can be compactly expressed by giving the transducer.

More details about transducers can be found on the all-knowing wiki (side note, the name transducer is also used to mean some completely different things in other fields).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.