1
$\begingroup$

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!

$\endgroup$
3
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Given $n$ in unary. $\endgroup$ – Yuval Filmus May 9 '17 at 17:45

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.