<p>I recently came accross the following standard inclusion of complexity classes:
<span class="math-container">$$\textbf{NC}^0 \subseteq \textbf{AC}^0 \subseteq \textbf{NC}^1 \subseteq \textbf{L} \subseteq \textbf{NL} \subseteq \textbf{NC}^2$$</span>
This confused me, since I always assumed circuit complexity classes are by definition non-uniform and hence those inclusions would fail for <span class="math-container">$\textbf{L}$</span> and <span class="math-container">$\textbf{NL}$</span>, 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, <span class="math-container">$\textbf{P}/\operatorname{poly}$</span>? Is this right? Is there a good criterion for when a circuit complexity class is defined to be uniform?</p>
<p>Alternatively, which are the natural non-uniform analogues of <span class="math-container">$\textbf{L}$</span> and <span class="math-container">$\textbf{NL}$</span>? Would this be <span class="math-container">$\textbf{L}/\operatorname{poly}$</span> and <span class="math-container">$\textbf{NL}/\operatorname{poly}$</span> or <span class="math-container">$\textbf{L}/\operatorname{log}$</span> and <span class="math-container">$\textbf{NL}/\operatorname{log}$</span>?</p>

CC BY-SA 4.0
2022-11-28T16:07:27.777Z
(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.
Emil Jeřábek
CC BY-SA 4.0
2022-11-28T22:28:31.350Z
@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?
Noel Arteche
CC BY-SA 4.0
2022-11-28T22:34:41.657Z
Sorry, I meant it does *not* make such assumptions clear.
Noel Arteche
CC BY-SA 4.0
2022-11-29T06:58:20.240Z
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.)
Emil Jeřábek
<cc.complexity-theory><complexity-classes><circuit-complexity><advice-and-nonuniformity><uniformity>
Non-uniformity assumptions in circuit complexity
Noel Arteche
# Non-uniformity assumptions in circuit complexity

(Asked by: username_0 on 2022-11-28)

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

**Tags:** cc.complexity-theory, complexity-classes, circuit-complexity, advice-and-nonuniformity, uniformity
> **Comments:**
> **username_1**: (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.  
> **username_0**: @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?  
> **username_0**: Sorry, I meant it does *not* make such assumptions clear.  
> **username_1**: 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.)  

---

## 0 answers

