See AC for definition.
Contains NL (hence also NC1). Contained in NC2. The complexity class DET also obeys all these containment relationships, but no containment is known in either direction between AC1 and DET.
The class of problems solvable by a nonuniform family of polynomial-size, polylog-depth circuits with unbounded-fanin XOR and bounded-fanin AND gates.
Defined in [GW96], where it was also shown that ⊕SAC1 contains SAC1.
ACi is the class of decision problems solvable by a nonuniform family of Boolean circuits, with polynomial size, depth O(logi(n)), and unbounded fanin. The gates allowed are AND, OR, and NOT.
Then AC is the union of ACi over all nonnegative i.
ACi is contained in NCi+1; thus, AC = NC.
For a random oracle A, (ACi)A is strictly contained in (ACi+1)A, and (uniform) ACA is strictly contained in PA, with probability 1 [Mil92].
FO-uniform AC with depth is equal to FO[].
The class of decision problems reducible in L to the problem of deciding membership in a context-free language.
Equals uniform SAC1 [Ven91]: LOGCFL is the class of decision problems solvable by a uniform family of AC1 circuits, in which no AND gate has fan-in exceeding 2 (see e.g. [Joh90], p. 137).
LOGCFL is closed under complement [BCD+89]. For more on LOGCFL from the descriptive complexity viewpoint, including completeness results under FO reductions, see [LMSV01].
Contains NL [Sud78], and also the problem of recognizing graphs of bounded tree-width [Wan94].
See NC for definition.
Contains AC1 and DET, both of which contain NL. It seems we currently (as of this writing, 15 Jun 2022) do not know any problem in NC2 that's not known to be in AC1∪ DET (see this question).
See SAC for definition.
Not closed under complement [BCD+89].
Not contained in ⊕SAC0 [K23].
See SAC for definition.
See TC for definition.
In addition to the different gatesets allowed in place of AND, OR, THR, also equivalent to arithmetic/counting analogue of AC1 modulo pn (the nth prime) [RT92].
