5
$\begingroup$

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?

$\endgroup$

1 Answer 1

8
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thanks, this answer is on point. Is there a concrete candidate in P but outside nuACC0? $\endgroup$ Oct 31, 2023 at 20:47
  • $\begingroup$ 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) $\endgroup$ Oct 31, 2023 at 21:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.