How to read $NC^1\subset L \subset NL \subset SAC^1$, $SAC^1=LOGCFL/poly$, and similar statements?

Question

The (complexity zoo) description of $NC^1$ says that it is contained in $L$, i.e. $NC^1\subset L$. The description of $SAC^1$ says that it is equal to $LOGCFL$$/poly$, i.e. $SAC^1=LOGCFL/poly$.

The wikipedia article on $LOGCFL$ says that it is situated between $NL$ and $AC^1$. I read this as $NL\subset LOGCFL\subset LOGCFL/poly=SAC^1\subset AC^1$, hence $NL\subset SAC^1$.

Obviously $L\subset NL$, so we get the nice summary $$NC^1\subset L \subset NL \subset SAC^1$$

But the statement $SAC^1=LOGCFL/poly$ makes me wonder, whether $NC^1\subset L$ or rather $$NC^1\subset L/poly \subset NL/poly \subset SAC^1$$

---

Honestly, I'm really unsure now. So I googled a bit, and found lecture notes introducing Boolean circuits with even more doubtful statements

The usual convention is not to count "not" gates in either of the above: one can show that all the "not" gates of a circuit can be pushed to immediately follow the input gates; thus, ignoring "not" gates affects the size by at most $n$ and the depth by at most $1$.

I heavily doubt that this statement is "exactly" true. I feel reminded of the wikipedia article on Fagin's lemma, and similar "sloppy CS statements". But how am I supposed to read such sloppy statements, and how can I guess what they are intended to mean?

Answer 1

The source of the confusion is probably uniformity. A circuit class like $\mathsf{NC}^1$ can be defined in two different ways:

1. Languages computed by bounded fan-in circuits of polynomial size and logarithmic depth.

2. Same as 1, only the circuits are uniform: there is an efficient Turing machine that on input $1^n$ generates the $n$th circuit.

The definition of uniformity is vague since there are several different definitions, many of them fitting the above description (with different definitions of efficient). The classic paper On uniformity within $\mathsf{NC}^1$ shows that many of these definition are in fact equivalent, and as far as I know, their common definition remains popular today. It often goes by the name "$\mathsf{AC}^0$-uniform".

If you want $\mathsf{NC}^1 \subseteq \mathsf{L}$ then you need the uniform version of $\mathsf{NC}^1$. If you want $\mathsf{NL}/poly \subseteq \mathsf{SAC}^1$ then you need the non-uniform version of $\mathsf{SAC}^1$.