2
$\begingroup$

Specifically I'm thinking about NC$^1$/poly and NC$^1$/rpoly (randomized advice). Are there any statements like

"If $\{C_n\}$ is a family of NC$^1$/(r)poly circuits with depth $C\log n$, then there exists a family $\{\tilde{C}_n\}$ of NC$^1$/(r)poly circuits with depth $\tilde{C}\log n$ such that $\tilde{C} < 1$ and $C_n(x) = \tilde{C}_n(x)$"?

Or would that be too powerful?

Improve this question
$\endgroup$
4
  • $\begingroup$ What is randomized advice? Is that stronger or weaker than normal advice? $\endgroup$
    – Emil Jeřábek
    May 4, 2022 at 6:51
  • $\begingroup$ As far as I can tell, with usual advice, i.e., non-uniform $\mathrm{NC}^1$ circuits, the statement is as false as possible: for any $d<n-\log n$ or so (such as $C\log n$), there exist functions computable by circuits of depth $d+1$, but not by circuits of depth $d$. Proof: if not, then all Boolean functions are computable by circuits of depth $d$, and therefore size $2^d$, as you can just take an arbitrary circuit, and keep reducing subcircuits of depth $d+1$ to $d$ until none remain. However, almost all functions require circuit size $\Omega(2^n/n)$. $\endgroup$
    – Emil Jeřábek
    May 4, 2022 at 7:04
  • $\begingroup$ Of course, with $\tilde C<1$ as written, it’s much easier to disprove: a circuit of depth $\tilde C\log n$ with $\tilde C<1$ has size at most $n^{\tilde C}<n$, hence it cannot even depend on all bits of the input. Thus, even simple functions such as $\mathrm{AND}(x_1,\dots,x_n)$ have no circuits of depth $\tilde C\log n$. $\endgroup$
    – Emil Jeřábek
    May 4, 2022 at 9:03
  • $\begingroup$ I see, this can't be true then. Thanks. $\endgroup$
    – trillianhaze
    May 4, 2022 at 11:52

0

Reset to default

Your Answer

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