patternMinor
Definition of uniform boolean circuit
Viewed 0 times
definitionuniformbooleancircuit
Problem
Definition
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#10161, answer score: 3
Revisions (0)
No revisions yet.