In Cook's famous paper on $\mathsf{NC}$, he cites the following result:

PROPOSITION 4.7 (Cook and Ruzzo, 1983). $\mathsf{AC}^k$ consists of those problems solvable by uniform unbounded fan-in circuit families in $O(\log^k n)$ depth and $n^{O(1)}$ size.

where $\mathsf{AC}^k$ here is defined for $k \ge 1$ as the class of problems solvable by an ATM in $O(\log n)$ space and $O(\log^k n)$ alternation depth. (Of course, the definition of $\mathsf{AC}^k$ usually goes the other way around, but given the equivalence it is all just a matter of presentation.)

Note the above is the logspace-uniform version of $\mathsf{AC}$. It was later acknowledged that for $\mathsf{AC}^0$ the more restrictive dlogtime-uniformity is preferable. There is also an interesting result regarding the (in)equality of dlogtime- and logspace-uniformity of $\mathsf{AC}^0$. We also know that dlogtime-uniform $\mathsf{AC}^0$ is characterizable as the class of problems solvable by ATMs in $O(\log n)$ time (instead of space above) and $O(1)$ alternation depth.

Given that dlogtime- and logspace-uniformity most likely does make a difference for $\mathsf{AC}^0$ I am interested whether the Cook and Ruzzo result can be extended to the case of $k = 0$ and logspace-uniform $\mathsf{AC}^0$. Unfortunately, in Cook's paper, "Cook and Ruzzo, 1983" is only listed as "unpublished theorem," so I was unable to check whether the proof also works for $k=0$ (and whether Cook and Ruzzo had simply neglected it for some reason).

  • $\begingroup$ Wouldn't PARITY be a counterexample? $\endgroup$ – sdcvvc Aug 6 '19 at 22:14
  • $\begingroup$ @sdcvvc Of course, the classic counterexample :) Make it an answer? I wonder now where exactly $k > 0$ is needed in the proof... $\endgroup$ – dkaeae Aug 7 '19 at 8:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.