3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Mar 21 '14 at 13:07
  • $\begingroup$ @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? $\endgroup$ – JohnnyCache Mar 21 '14 at 13:24
  • 1
    $\begingroup$ I guess you're right... it appears that the difference between logspace-uniform and P-uniform is more important for restricted classes of circuits. $\endgroup$ – Yuval Filmus Mar 21 '14 at 20:12
1
$\begingroup$

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

The same phenomenon occurs whenever we have a universal circuit (in the case of P, this is the circuit solving CVP). For a recent example, see this paper on comparator circuits.

$\endgroup$

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.