<p>Most people would believe that DTIME(n) contains problems that are not in non-uniform ACC^0 (poly size). One reason is that the containment of DTIME(n) in non-uniform ACC^0 implies P is contained in non-uniform ACC^0, by a padding argument. We don't even believe that P = NC (arbitrary time t can be simulated in parallel time polylog t), which would be a weaker equality.</p>
<p>Nevertheless, it is open if DTIME(n) is in P-uniform ACC^0, or not. In fact it is open if NP is in P-uniform ACC^0. I don't think this particular open problem is evidence for the power of ACC^0 but rather the lack of techniques to attack ACC^0. (Although I have started to think that ACC^0 could potentially contain TC^0, I don't think it could contain P :))</p>
<p>Cody Murray and I already pushed the lower bound to NTIME(n^polylog n) not in ACC^0, back in 2018. There have been many follow-ups since then as well, improving on these lower bounds in various ways. Going below NTIME(n^polylog n) to NP seems to require a different approach altogether, but it's unclear to me that radically new ideas are needed. Especially once you allow the circuits to be P-uniform. The main bottleneck is probably the translation of polynomial-size ACC^0 to SYM-AND of quasi-polynomial size, which has been used in basically all ACC^0 lower bounds since 2010.</p>

CC BY-SA 4.0
2023-10-31T20:47:31.863Z
Thanks, this answer is on point. Is there a concrete candidate in P but outside nuACC0?
Nicholas Brandt
CC BY-SA 4.0
2023-10-31T21:31:15.283Z
Sure: P is not in nuACC^0 iff the Circuit Evaluation problem is not in nuACC^0. (Fun and very general exercise if you haven't seen it before)
Ryan Williams
CC BY-SA 4.0
2023-10-31T16:21:10.563Z
2023-10-31T16:21:10.563Z
Ryan Williams
<p>In a breakthrough Ryan Williams (STOC13/14) showed that <span class="math-container">$\mathsf{NEXP} \nsubseteq \text{non-uniform } \mathsf{ACC}^0$</span>.</p>
<p>How far can we potentially push this result?
In other words, what is the largest <span class="math-container">$f$</span> such that we know/believe</p>
<ol>
<li><span class="math-container">$\mathsf{DTIME}[f(n)] \subseteq \text{non-uniform } \mathsf{ACC}^0$</span>, or</li>
<li><span class="math-container">$\mathsf{DTIME}[f(n)] \subseteq \mathsf{P}\text{-uniform } \mathsf{ACC}^0$</span>?</li>
</ol>
<p>Obviously, both hold for <span class="math-container">$f(n)=\Theta(1)$</span> and both are false for <span class="math-container">$f(n)=2^{2^{n^{\Theta(1)}}}$</span> because <span class="math-container">$\mathsf{NEXP} \subseteq \mathsf{DTIME}[2^{2^{n^{\Theta(1)}}}]$</span>.
Unfortunately, I could not find a good source for this.
Section 14.4.2 in the Arora-Barak textbook lists some results about <span class="math-container">$\mathsf{ACC}^0$</span> but only for specific modulus or relation to other <em>circuit</em> classes, e.g. <span class="math-container">$\mathsf{ACC}^0 \subseteq \mathsf{NC}^1$</span>.</p>
<p>Concrete bonus question: Is <span class="math-container">$\mathsf{DTIME}[n] \subseteq \mathsf{P}\text{-uniform } \mathsf{ACC}^0$</span> known?</p>

<complexity-classes><circuit-complexity><fine-grained>
Relation between ACC^0 and DTIME
Nicholas Brandt
# Relation between ACC^0 and DTIME

(Asked by: username_0 on 2023-10-31)

In a breakthrough Ryan Williams (STOC13/14) showed that $\mathsf{NEXP} \nsubseteq \text{non-uniform } \mathsf{ACC}^0$.

How far can we potentially push this result?
In other words, what is the largest $f$ such that we know/believe

1. $\mathsf{DTIME}[f(n)] \subseteq \text{non-uniform } \mathsf{ACC}^0$, or
2. $\mathsf{DTIME}[f(n)] \subseteq \mathsf{P}\text{-uniform } \mathsf{ACC}^0$?

Obviously, both hold for $f(n)=\Theta(1)$ and both are false for $f(n)=2^{2^{n^{\Theta(1)}}}$ because $\mathsf{NEXP} \subseteq \mathsf{DTIME}[2^{2^{n^{\Theta(1)}}}]$.
Unfortunately, I could not find a good source for this.
Section 14.4.2 in the Arora-Barak textbook lists some results about $\mathsf{ACC}^0$ but only for specific modulus or relation to other *circuit* classes, e.g. $\mathsf{ACC}^0 \subseteq \mathsf{NC}^1$.

Concrete bonus question: Is $\mathsf{DTIME}[n] \subseteq \mathsf{P}\text{-uniform } \mathsf{ACC}^0$ known?

**Tags:** complexity-classes, circuit-complexity, fine-grained

---

## 1 answers

### Answer by username_1 on 2023-10-31. Score: 8 | Accepted answer

Most people would believe that DTIME(n) contains problems that are not in non-uniform ACC^0 (poly size). One reason is that the containment of DTIME(n) in non-uniform ACC^0 implies P is contained in non-uniform ACC^0, by a padding argument. We don't even believe that P = NC (arbitrary time t can be simulated in parallel time polylog t), which would be a weaker equality.

Nevertheless, it is open if DTIME(n) is in P-uniform ACC^0, or not. In fact it is open if NP is in P-uniform ACC^0. I don't think this particular open problem is evidence for the power of ACC^0 but rather the lack of techniques to attack ACC^0. (Although I have started to think that ACC^0 could potentially contain TC^0, I don't think it could contain P :))

Cody Murray and I already pushed the lower bound to NTIME(n^polylog n) not in ACC^0, back in 2018. There have been many follow-ups since then as well, improving on these lower bounds in various ways. Going below NTIME(n^polylog n) to NP seems to require a different approach altogether, but it's unclear to me that radically new ideas are needed. Especially once you allow the circuits to be P-uniform. The main bottleneck is probably the translation of polynomial-size ACC^0 to SYM-AND of quasi-polynomial size, which has been used in basically all ACC^0 lower bounds since 2010.

> **Comments:**
> **username_0**: Thanks, this answer is on point. Is there a concrete candidate in P but outside nuACC0?  
> **username_1**: Sure: P is not in nuACC^0 iff the Circuit Evaluation problem is not in nuACC^0. (Fun and very general exercise if you haven't seen it before)  

---

