<p>$\mathsf{AC,ACC,TC}$-hierarchy are basic bounded depth circuit hierarchies.</p>

<p>$AC$-hierarchy is $\bigcup _{i =0}^{\infty}  AC^{i} $ , where $AC^{i}$ is the $i$-th level of the hierarchy: a family of $\mathsf{poly} (n)$-size and $O(\log ^{i}n)$ depth circuits with AND OR NOT gates. $ACC$-hierarchy is obtained by adding $AC$-hierarchy  modulo gates computing the number of $1$'s in a input mod $q$ is $0$ or not for fixed integer $q$. $\mathsf{TC}$-hierarchy is $\bigcup _{i=0}^{\infty}  TC^{i} $ , where $TC^{i}$ is the $i$-th level of the hierarchy: a family of $\mathsf{poly} (n)$-size and $O(\log ^{i}n)$ depth circuits with threshold gates. <em>We consider classes of nonuniform circuits</em></p>

<p>I am interested in conditional results saying that if I were a bird, then blah blah...</p>

<p>More specifically, let $\mathcal{A,B}$ be large compleixty classes satisfying 
$\mathcal{A} \subseteq  \mathcal{B}$ and let $H^{i}$ be the $i$^th level of a bounded depth circuit hierarchy $H$. Is there a result saying that if $H \supseteq  \mathcal{B}  $ then $H^{i} \supseteq \mathcal{A} $ for a fixed  $i$ ?</p>

<p>More concretely, is there a well know complexity class $\mathcal{L} $ with the result that if $\mathsf{NEXP} \subseteq H$ then $\mathcal{L} \subseteq  H^{0}$ ?</p>

CC BY-SA 3.0
2013-05-02T22:52:06.840Z
Assuming we are talking about uniform versions, all of these hierarchies are inside $\mathsf{P}$ which is strictly contained in $\mathsf{Exp}$. So you can get any statement by  that assumption.
Kaveh
CC BY-SA 3.0
2013-05-16T16:01:25.377Z
If you parameterize the classes with size in place of depth then we have: Eric Allender and Michal Koucký, "[Amplifying Lower Bounds by Means of Self-Reducibility](http://ftp.cs.rutgers.edu/pub/allender/amplifying.pdf)", 2008
Kaveh
<cc.complexity-theory><complexity-classes><conditional-results><advice-and-nonuniformity>
Conditional Results on Bounded Depth Circuit Hierarchy
echuly
# Conditional Results on Bounded Depth Circuit Hierarchy

(Asked by: username_0 on 2013-05-02)

$\mathsf{AC,ACC,TC}$-hierarchy are basic bounded depth circuit hierarchies.

$AC$-hierarchy is $\bigcup \_{i =0}^{\infty} AC^{i} $ , where $AC^{i}$ is the $i$-th level of the hierarchy: a family of $\mathsf{poly} (n)$-size and $O(\log ^{i}n)$ depth circuits with AND OR NOT gates. $ACC$-hierarchy is obtained by adding $AC$-hierarchy modulo gates computing the number of $1$'s in a input mod $q$ is $0$ or not for fixed integer $q$. $\mathsf{TC}$-hierarchy is $\bigcup \_{i=0}^{\infty} TC^{i} $ , where $TC^{i}$ is the $i$-th level of the hierarchy: a family of $\mathsf{poly} (n)$-size and $O(\log ^{i}n)$ depth circuits with threshold gates. *We consider classes of nonuniform circuits*

I am interested in conditional results saying that if I were a bird, then blah blah...

More specifically, let $\mathcal{A,B}$ be large compleixty classes satisfying
$\mathcal{A} \subseteq \mathcal{B}$ and let $H^{i}$ be the $i$^th level of a bounded depth circuit hierarchy $H$. Is there a result saying that if $H \supseteq \mathcal{B} $ then $H^{i} \supseteq \mathcal{A} $ for a fixed $i$ ?

More concretely, is there a well know complexity class $\mathcal{L} $ with the result that if $\mathsf{NEXP} \subseteq H$ then $\mathcal{L} \subseteq H^{0}$ ?

**Tags:** cc.complexity-theory, complexity-classes, conditional-results, advice-and-nonuniformity
> **Comments:**
> **username_1**: Assuming we are talking about uniform versions, all of these hierarchies are inside $\mathsf{P}$ which is strictly contained in $\mathsf{Exp}$. So you can get any statement by  that assumption.  
> **username_1**: If you parameterize the classes with size in place of depth then we have: Eric Allender and Michal Koucký, "[Amplifying Lower Bounds by Means of Self-Reducibility](http://ftp.cs.rutgers.edu/pub/allender/amplifying.pdf)", 2008  

---

## 0 answers

