2
$\begingroup$

$\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}$ ?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Kaveh May 2 '13 at 22:52
  • 1
    $\begingroup$ 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", 2008 $\endgroup$ – Kaveh May 16 '13 at 16:01

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.