<p>Let <span class="math-container">$d \in \mathbb{N}$</span> be arbitrary. Let <span class="math-container">$\mathsf{AC^0_d}$</span>-Eval be the following promise problem:</p>
<p><strong>Input:</strong> A depth <span class="math-container">$d$</span> formula <span class="math-container">$\varphi(x)$</span> and a binary string <span class="math-container">$a$</span>.<br />
<strong>Output:</strong> <span class="math-container">$\varphi(a)$</span></p>
<p>I am looking for a reference to cite for <span class="math-container">$\mathsf{AC^0_d}$</span>-Eval
<span class="math-container">$\in \mathsf{FO}$</span>.</p>
<hr />
<h3>Notes</h3>
<ol>
<li><p><span class="math-container">$\mathsf{FO} = \mathsf{LH} = \mathsf{AltTime}(O(1), O(\lg n)) = \mathsf{DLogTimeUniform\ AC^0}$</span>.</p>
</li>
<li><p><span class="math-container">$\mathsf{AltTime}(a(n), t(n))$</span> is the class of alternating Tuition machines with at most <span class="math-container">$a(n)$</span> alternations and <span class="math-container">$t(n)$</span> 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, &quot;On uniform circuit complexity&quot;, 1981.</p>
</li>
</ol>

CC BY-SA 3.0
2016-01-29T18:32:33.720Z
Nothing of interest to be found in Vollmer's book?
Michaël Cadilhac
CC BY-SA 3.0
2016-01-30T10:57:01.730Z
@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.
Kaveh
CC BY-SA 3.0
2016-01-30T10:59:08.967Z
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.
Kaveh
CC BY-SA 3.0
2016-01-30T14:17:07.707Z
Thanks for asking this question. Note that in [wikipedia, AltTime is written ATime, and the arguments are swapped](https://en.wikipedia.org/wiki/Alternating_Turing_machine#Definition), just in case the swapping was not intentional.
Thomas Klimpel
<cc.complexity-theory><reference-request><lo.logic><circuit-complexity><ac0>
The evaluation problem for AC$^0_d$ formulas is in FO
Kaveh
# The evaluation problem for AC$^0_d$ formulas is in FO

(Asked by: username_0 on 2016-01-29)

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

---

### Notes

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.

**Tags:** cc.complexity-theory, reference-request, lo.logic, circuit-complexity, ac0

> **Comments:**
> **username_1**: Nothing of interest to be found in Vollmer's book?  
> **username_0**: @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.  
> **username_0**: 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.  
> **username_2**: Thanks for asking this question. Note that in [wikipedia, AltTime is written ATime, and the arguments are swapped](https://en.wikipedia.org/wiki/Alternating_Turing_machine#Definition), just in case the swapping was not intentional.  

---

## 0 answers

