Class Description

SAC1: Semi-Unbounded-Fanin AC1

See SAC for definition.

Equals LOGCFL/poly [Ven91].

Contained in ⊕SAC1 [GW96].

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


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