# Relation between logspace-uniform circuits and P-uniform circuits

In the book "Computational complexity" of Barak and Arora, on page 112, they state that:

Theorem 6.15: A language has logspace-uniform circuits of polynomial size iff it is in P.

The proof of this one is left as an exercise to the reader. I think both directions are trivial:

=> seems trivial, as a logspace TM that generates a circuit also runs in polynomial time, and hence is a P-uniform circuit, which is part of P.

<= seems trivial, as a language that has a polynomial-time TM can be transformed into a circuit with Cook-Levin's theorem in logspace.

However, what I don't get is why the theorem 6.15 explicitly states that the circuits must be of "polynomial size". How can there exist a logspace-uniform circuit that isn't polynomial in size? The logspace computable function itself cannot exceed a polynomial bound, how can it produce a circuit of superpolynomial size?

Also, this theorem would imply that logspace-uniform circuits comprise the same languages as P-uniform circuits, which seems very unintuitive to me. I can't find any information on the relation between logspace-uniform and P-space uniform circuits on the web, so my assumption that they are equal is probably false, but I fail to see see why.

• You're right that any logspace-uniform family of circuits has polynomial size, so this qualification doesn't seem to be necessary. On the other hand, the same is not true for P-uniform circuits, which could be superpolynomial in size. Mar 21, 2014 at 13:07
• @YuvalFilmus: Thanks for the reply! I still don't fully get it though: a P-uniform circuit is generated in polynomial time, how can the result be larger than a polynomial? Could you give me a small example of such a circuit? Mar 21, 2014 at 13:24
• I guess you're right... it appears that the difference between logspace-uniform and P-uniform is more important for restricted classes of circuits. Mar 21, 2014 at 20:12

The circuit value problem (CVP) is, given a circuit and an input, to evaluate the circuit. This is a well-known problem which is P-complete with respect to AC$^0$ reductions. Thus one can define P as the class of problems AC$^0$-reducible to CVP. We get the same class if we consider the class of problems polytime-reducible to CVP, or in general $L$-reducible to CVP, where $L$ is any intermediate class between AC$^0$ and P. An $L$-reduction to CVP is very similar to an $L$-uniform circuit (the only difference is that the inputs to the circuit could be any $L$-functions). Specifically, an AC$^0$-reduction to CVP can be converted to a uniform circuit (the notion of uniformity depends on the exact format of circuits, but it can probably be taken all the way down to AC$^0$).
• Since comparator circuits cannot duplicate inputs, in order to make this question meaningful you need to consider a different class of circuits in which input duplication is allowed. This is one of the reasons why the paper considers the $\mathsf{AC^0}$-closure of functions computed by comparator circuits. Apr 20, 2021 at 13:43
• If you allow duplicating inputs (as well as negating them), then you can clearly embed formulas, and so $\mathsf{AC^0}$, in $\mathsf{CC^1}$. On the other hand, it seems that even the OR function on $n$ inputs isn't in $\mathsf{CC^0}$. Apr 20, 2021 at 13:44