I recently came accross the following standard inclusion of complexity classes: $$\textbf{NC}^0 \subseteq \textbf{AC}^0 \subseteq \textbf{NC}^1 \subseteq \textbf{L} \subseteq \textbf{NL} \subseteq \textbf{NC}^2$$ This confused me, since I always assumed circuit complexity classes are by definition non-uniform and hence those inclusions would fail for $\textbf{L}$ and $\textbf{NL}$, which are uniform. Given that this chain of inclusion seems to show up in many texts, I imagine that, in fact, circuit classes tend to be uniform except for, perhaps, $\textbf{P}/\operatorname{poly}$? Is this right? Is there a good criterion for when a circuit complexity class is defined to be uniform?

Alternatively, which are the natural non-uniform analogues of $\textbf{L}$ and $\textbf{NL}$? Would this be $\textbf{L}/\operatorname{poly}$ and $\textbf{NL}/\operatorname{poly}$ or $\textbf{L}/\operatorname{log}$ and $\textbf{NL}/\operatorname{log}$?

  • 3
    $\begingroup$ (1) Whether classes like $\mathrm{NC}^i$ are meant to be uniform or nonuniform depends on the context and the author; ideally, this should be made clear somewhere in the introduction to the paper. XXX/poly is explicitly nonuniform (more precisely, using polynomial advice). (2) Definitely $\mathrm{L/poly}$ and $\mathrm{NL/poly}$. These can be alternatively characterized as classes of languages computable by sequences of poynomial-size deterministic/nondeterministic branching programs. $\endgroup$ Nov 28, 2022 at 16:07
  • $\begingroup$ @EmilJeřábek Thanks! I was precisely confused because the paper I am currently reading does make such assumptions clear but then goes on to use inclusions like the ones above. In fact, it seems like they switch between the two conventions whenever convenient... Is it the case that, when taking the classes to be non-uniform, the previous chain of inclusions holds but replacing L and NL for L/poly and NL/poly? Or do those two classes get placed somewhere else? $\endgroup$ Nov 28, 2022 at 22:28
  • $\begingroup$ Sorry, I meant it does not make such assumptions clear. $\endgroup$ Nov 28, 2022 at 22:34
  • 1
    $\begingroup$ The chain of inclusions suggests they view the classes as uniform. It is quite unusual, though I guess not impossible, for L and NL to denote nonuniform classes. But yes, the chain also holds for nonuniform classes with L/poly and NL/poly in place of L and NL. (Any inclusion between classes continues to hold if you give them the same amount of advice.) $\endgroup$ Nov 29, 2022 at 6:58


Your Answer

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