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

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