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


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

  • 3
    $\begingroup$ How is the input represented? $\endgroup$ – András Salamon Jun 22 '13 at 16:09
  • 4
    $\begingroup$ 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). $\endgroup$ – Ryan Williams Jun 22 '13 at 20:36
  • $\begingroup$ @András, I added a clarification. $\endgroup$ – Kaveh Jun 22 '13 at 21:19
  • $\begingroup$ @Ryan, I added a clarification. I think any reasonable encoding will work for me. $\endgroup$ – Kaveh Jun 22 '13 at 21:24

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.