<p>Is the evaluation problem for <span class="math-container">$\mathsf{AC}^0_d$</span> circuits in <span class="math-container">$\mathsf{AC}^0_{d+1}$</span>? What is the least depth <span class="math-container">$k(d)$</span> such that the evaluation of an <span class="math-container">$\mathsf{AC}^0_d$</span> circuits can be computed in <span class="math-container">$\mathsf{AC}^0_{k(d)}$</span>?</p>
<p>How about the evaluation problem for <span class="math-container">$\mathsf{TC}^0_d$</span> circuits?</p>
<p>By evaluation problem for a complexity class <span class="math-container">$C$</span> I mean the following promise problem:</p>
<blockquote>
<p>Given a circuit <span class="math-container">$c\in C$</span> and an input <span class="math-container">$x$</span> for <span class="math-container">$c$</span>,<br />
Output the value of <span class="math-container">$c(x)$</span>.</p>
</blockquote>
<h3>Clarification</h3>
<p>I don't need any particular input format, I can change other parts to use a similar encoding of circuits. So as long as the encoding is something reasonable it is good for me. By reasonable I mean it should be easy to do simple manipulations of circuits, e.g. given the code for two circuits it should be easy to determine the number of nodes in the circuits, given a circuit and <span class="math-container">$i$</span> determine the type of gate <span class="math-container">$i$</span> and its parents, etc.</p>
<p>For example, any of the following would work for me:</p>
<ol>
<li><p>circuit is encoded as the adjacency matrix of the connection graphs where gates are numbered from <span class="math-container">$1$</span> to <span class="math-container">$n$</span>, there is no wire from <span class="math-container">$g_i$</span> to <span class="math-container">$g_j$</span> then <span class="math-container">$i&gt;j$</span>, and the list of gate types. You can also assume that the number of gates and the size of the input are also provided (in unary).</p>
</li>
<li><p>the direct connection language of the circuit (which is used in the definition of <span class="math-container">$\mathsf{DLogTime}$</span>-uniformity of circuits),</p>
</li>
<li><p>the extended connection language of the circuit (which is used in the definition of <span class="math-container">$\mathsf{DLogTime}$</span>-uniformity for <span class="math-container">$\mathsf{NC^1}$</span>).</p>
</li>
</ol>

CC BY-SA 3.0
2013-06-22T16:09:01.810Z
How is the input represented?
András Salamon
CC BY-SA 3.0
2013-06-22T20:36:06.993Z
Andras' question is indeed important. I thought about this question a couple of years ago and believe I concluded that $k(d)=d+1$ for both $AC^0$ and $TC^0$, using the appropriate input representation (which is crucial).
Ryan Williams
CC BY-SA 3.0
2013-06-22T21:19:25.547Z
@András, I added a clarification.
Kaveh
CC BY-SA 3.0
2013-06-22T21:24:17.303Z
@Ryan, I added a clarification. I think any reasonable encoding will work for me.
Kaveh
<cc.complexity-theory><reference-request><circuit-complexity><bounded-depth>
Evaluation of bounded-depth circuits
Kaveh
# Evaluation of bounded-depth circuits

(Asked by: username_0 on 2013-06-21)

Is the evaluation problem for $\mathsf{AC}^0\_d$ circuits in $\mathsf{AC}^0\_{d+1}$? What is the least depth $k(d)$ such that the evaluation of an $\mathsf{AC}^0\_d$ circuits can be computed in $\mathsf{AC}^0\_{k(d)}$?

How about the evaluation problem for $\mathsf{TC}^0\_d$ circuits?

By evaluation problem for a complexity class $C$ I mean the following promise problem:

> Given a circuit $c\in C$ and an input $x$ for $c$,  
> Output the value of $c(x)$.

### Clarification

I don't need any particular input format, I can change other parts to use a similar encoding of circuits. So as long as the encoding is something reasonable it is good for me. By reasonable I mean it should be easy to do simple manipulations of circuits, e.g. given the code for two circuits it should be easy to determine the number of nodes in the circuits, given a circuit and $i$ determine the type of gate $i$ and its parents, etc.

For example, any of the following would work for me:

1. circuit is encoded as the adjacency matrix of the connection graphs where gates are numbered from $1$ to $n$, there is no wire from $g\_i$ to $g\_j$ then $i>j$, and the list of gate types. You can also assume that the number of gates and the size of the input are also provided (in unary).
2. the direct connection language of the circuit (which is used in the definition of $\mathsf{DLogTime}$-uniformity of circuits),
3. the extended connection language of the circuit (which is used in the definition of $\mathsf{DLogTime}$-uniformity for $\mathsf{NC^1}$).

**Tags:** cc.complexity-theory, reference-request, circuit-complexity, bounded-depth
> **Comments:**
> **username_1**: How is the input represented?  
> **username_2**: Andras' question is indeed important. I thought about this question a couple of years ago and believe I concluded that $k(d)=d+1$ for both $AC^0$ and $TC^0$, using the appropriate input representation (which is crucial).  
> **username_0**: @András, I added a clarification.  
> **username_0**: @Ryan, I added a clarification. I think any reasonable encoding will work for me.  

---

## 0 answers

