2
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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