# What does $L$-uniformity mean?

I've understood that $L$-uniformity means that there's a TM that can output the description of $C_n$ in $O(\log n)$ space. Now, that seems odd to me since the description itself (as far as I understand) must be a $O(n)$. I'd be glad for clarification.

Also, in that context: What does $L$-uniform $NC^k$ means?

Thanks!

What is usually meant by saying that a (not necessarily binary) function is computable in $O(\log n)$ space, is that there exists a Turing machine computing it which uses only $O(\log n)$ space in its work tape. This limitation does not concern the output tape, which is write only. You can also think of this condition as being able to, given $i$, output the $i$'th bit of the circuits description using only $O(\log n)$ space.
A circuit family $\{c_n\}_{n\in\mathbb{N}}$ is logspace uniform $NC^k$ iff $c_n$ is a circuit with $n$ inputs of size $poly(n)$ and depth $O(\log ^k n)$, and additionally, there exists a logspace Turing machine such that given $1^n$ as input, outputs a description of $c_n$.
• Given $n$ in unary. May 9 '17 at 17:45