<p>(In this question, &quot;uniform&quot; will mean <span class="math-container">$DLOGTIME$</span>-uniform.)</p>
<p>In Allender's 1998 paper &quot;The Permanent Requires Large Uniform Threshold Circuits&quot;, he talks about the &quot;exponential versions&quot; of uniform constant-depth circuit complexity classes. In particular:</p>
<ul>
<li>The exponential version of uniform <span class="math-container">$AC^0$</span> is the polynomial hierarchy <span class="math-container">$PH$</span>, which is the closure of all languages <span class="math-container">$A \in P$</span> with the operations <span class="math-container">$NP^A$</span> and <span class="math-container">$coNP^A$</span>.</li>
<li>The exponential version of uniform <span class="math-container">$ACC^0$</span> is <span class="math-container">$ModPH$</span>, which is the closure of languages <span class="math-container">$A \in P$</span> with operations <span class="math-container">$NP^A$</span>, <span class="math-container">$coNP^A$</span>, and <span class="math-container">$Mod_mP^A$</span>, where the latter is defined as the set of languages <span class="math-container">$B$</span> such that there exists a nondeterministic Turing machine <span class="math-container">$M$</span> such that <span class="math-container">$x \in B$</span> if and only if <span class="math-container">$M^A$</span> accepts <span class="math-container">$x$</span> on a number of computational paths divisible by <span class="math-container">$m$</span>.</li>
<li>The exponential version of uniform <span class="math-container">$TC^0$</span> is the counting hierarchy, which is the union of <span class="math-container">$PP, PP^{PP}, PP^{PP^{PP}}, ...$</span></li>
</ul>
<p>And by &quot;exponential&quot;, it is meant that the larger classes listed above can be interpreted as alternating Turing machines with existential/universal, existential/universal/modular counting, and majority states respectively, making <span class="math-container">$O(1)$</span> alternations, and computing with polynomial time -- and if the time is reduced to logarithmic, the corresponding uniform constant-depth circuit classes are obtained instead.</p>
<p>What I couldn't find any mention of (in any paper) is what the exponential version of <span class="math-container">$CC^0$</span> is called -- that is, the closure of all languages <span class="math-container">$A \in P$</span> under <span class="math-container">$Mod_mP^A$</span>. Is there a name for this class, or other papers about it? I'm especially curious about whether equality between this class and <span class="math-container">$ModPH$</span> is known, as an exponential analog of <span class="math-container">$CC^0$</span> vs <span class="math-container">$ACC^0$</span>.</p>

CC BY-SA 4.0
2023-09-29T22:53:14.057Z
Indeed, based on the intuition that one can glean from https://iuuk.mff.cuni.cz/~koucky/papers/acc.pdf it might be possible to show that the class you're asking about is actually equal to $ModPH$.  One way to attempt this would be to show that uniform $ACC^0$ can be solved by uniform (deterministic) quasipolynomial-size $CC^0$ circuits.  This would be interesting.  I think that it would probably require a few new ideas, though.
Eric Allender
CC BY-SA 4.0
2022-12-07T12:41:44.007Z
Languages in this class are called “$\oplus$-ptime predicates” in Buss, [Uniform proofs of ACC representations](https://mathweb.ucsd.edu/~sbuss/ResearchWeb/uniformACC/), but I don’t think this is a particularly standard name. In any case, it is very close to ModPH: if you denote the class as $C$, then $\mathrm{ModPH=BP\cdot{}}C$.
Emil Jeřábek
<reference-request><nondeterminism><polynomial-hierarchy>
Exponential version of $CC^0$
Jake
# Exponential version of $CC^0$

(Asked by: username_0 on 2022-12-07)

(In this question, "uniform" will mean $DLOGTIME$-uniform.)

In Allender's 1998 paper "The Permanent Requires Large Uniform Threshold Circuits", he talks about the "exponential versions" of uniform constant-depth circuit complexity classes. In particular:

* The exponential version of uniform $AC^0$ is the polynomial hierarchy $PH$, which is the closure of all languages $A \in P$ with the operations $NP^A$ and $coNP^A$.
* The exponential version of uniform $ACC^0$ is $ModPH$, which is the closure of languages $A \in P$ with operations $NP^A$, $coNP^A$, and $Mod\_mP^A$, where the latter is defined as the set of languages $B$ such that there exists a nondeterministic Turing machine $M$ such that $x \in B$ if and only if $M^A$ accepts $x$ on a number of computational paths divisible by $m$.
* The exponential version of uniform $TC^0$ is the counting hierarchy, which is the union of $PP, PP^{PP}, PP^{PP^{PP}}, ...$

And by "exponential", it is meant that the larger classes listed above can be interpreted as alternating Turing machines with existential/universal, existential/universal/modular counting, and majority states respectively, making $O(1)$ alternations, and computing with polynomial time -- and if the time is reduced to logarithmic, the corresponding uniform constant-depth circuit classes are obtained instead.

What I couldn't find any mention of (in any paper) is what the exponential version of $CC^0$ is called -- that is, the closure of all languages $A \in P$ under $Mod\_mP^A$. Is there a name for this class, or other papers about it? I'm especially curious about whether equality between this class and $ModPH$ is known, as an exponential analog of $CC^0$ vs $ACC^0$.

**Tags:** reference-request, nondeterminism, polynomial-hierarchy

> **Comments:**
> **username_2**: Languages in this class are called “$\oplus$-ptime predicates” in Buss, [Uniform proofs of ACC representations](https://mathweb.ucsd.edu/~sbuss/ResearchWeb/uniformACC/), but I don’t think this is a particularly standard name. In any case, it is very close to ModPH: if you denote the class as $C$, then $\mathrm{ModPH=BP\cdot{}}C$.  
> **username_1**: Indeed, based on the intuition that one can glean from https://iuuk.mff.cuni.cz/~koucky/papers/acc.pdf it might be possible to show that the class you're asking about is actually equal to $ModPH$.  One way to attempt this would be to show that uniform $ACC^0$ can be solved by uniform (deterministic) quasipolynomial-size $CC^0$ circuits.  This would be interesting.  I think that it would probably require a few new ideas, though.  

---

## 0 answers

