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

Improve this question
$\endgroup$
3
  • $\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
    Commented Mar 21, 2014 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
    Commented Mar 21, 2014 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
    Commented Mar 21, 2014 at 20:12

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
18
  • $\begingroup$ Is AC^0 in CC^0 or CC^1? I tried to find references but could not. AC^i and CC^j are incomparable if i>0 as your paper says or else we know NC and CC are comparable. But is it true at i=0? $\endgroup$
    – Turbo
    Commented Apr 20, 2021 at 9:33
  • $\begingroup$ 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. $\endgroup$
    – Yuval Filmus
    Commented Apr 20, 2021 at 13:43
  • $\begingroup$ 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}$. $\endgroup$
    – Yuval Filmus
    Commented Apr 20, 2021 at 13:44
  • $\begingroup$ isn't or not in cc0 a famous problem? Is there a proof anywhere cc hierarchy is infinite with respect to an oracle? Cc is only a mod2 mod3 based circuit right and it seems pretty simple and what evidence is there it is infinite? $\endgroup$
    – Turbo
    Commented Apr 20, 2021 at 20:25
  • $\begingroup$ The complexity class CC isn't so popular. $\endgroup$
    – Yuval Filmus
    Commented Apr 20, 2021 at 20:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.