Class Description

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

Linked From 1 Classes

SAC1: Semi-Unbounded-Fanin AC1

See SAC for definition.

Equals LOGCFL/poly [Ven91].

Contained in ⊕SAC1 [GW96].

More about...