Class Description

AC1: Unbounded Fanin Log-Depth Circuits

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.

Linked From

⊕SAC1: AC1 With Unbounded Parity Gates

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.

More about...


AC: Unbounded Fanin Polylogarithmic-Depth Circuits

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.

AC1 contains NL.

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[].

More about...


LOGCFL: Logarithmically Reducible to CFL

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

More about...


NC2: Level 2 of NC

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 AC1DET (see this question).

More about...


SAC0: Semi-Unbounded-Fanin AC0

See SAC for definition.

Not closed under complement [BCD+89].

Not contained in ⊕SAC0 [K23].

SAC1: Semi-Unbounded-Fanin AC1

See SAC for definition.

Equals LOGCFL/poly [Ven91].

Contained in ⊕SAC1 [GW96].

More about...


TC1: Log-depth Threshold Circuits

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

More about...