Let $d \in \mathbb{N}$ be arbitrary. Let $\mathsf{AC^0_d}$-Eval be the following promise problem:

Input: A depth $d$ formula $\varphi(x)$ and a binary string $a$.
Output: $\varphi(a)$

I am looking for a reference to cite for $\mathsf{AC^0_d}$-Eval $\in \mathsf{FO}$.


  1. $\mathsf{FO} = \mathsf{LH} = \mathsf{AltTime}(O(1), O(\lg n)) = \mathsf{DLogTimeUniform\ AC^0}$.

  2. $\mathsf{AltTime}(a(n), t(n))$ is the class of alternating Tuition machines with at most $a(n)$ alternations and $t(n)$ time. Some authors use other notations like ATime, AAltTime, ATimeAlt, etc. to refer to the class of alternating Turning machines with bounds on alternations and time. For details of the definition of alternating Turing machines with small amount of resources refer to Ruzzo, "On uniform circuit complexity", 1981.

  • $\begingroup$ Nothing of interest to be found in Vollmer's book? $\endgroup$ – Michaël Cadilhac Jan 29 '16 at 18:32
  • $\begingroup$ @MichaëlCadilhac, I checked Vollmer and a couple of other books but I couldn't find it in them. I think people don't mention this because without the promise it is not clear how to check if the input is an appropriate circuit and second they typically do not go below AC0. $\endgroup$ – Kaveh Jan 30 '16 at 10:57
  • $\begingroup$ I can refer to something like Sam Buss's ALogTime=AltTime$(O(\lg n), O(\lg n))$ algorithm for BFE and say that we can ignore the checking part since it is a promise and for the evaluation part we can stop the process after a constant number of alternations since we know the depth is $d$ but I would prefer to cite a reference if there is one. $\endgroup$ – Kaveh Jan 30 '16 at 10:59
  • $\begingroup$ Thanks for asking this question. Note that in wikipedia, AltTime is written ATime, and the arguments are swapped, just in case the swapping was not intentional. $\endgroup$ – Thomas Klimpel Jan 30 '16 at 14:17

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.