Class Description

SAC: Semi-Unbounded-Fanin AC

SAC^k is the class of decision problems solvable by a family of depth-O(log^kn) circuits with unbounded-fanin OR & bounded-fanin AND gates. Negations are only allowed at the input level.

A uniformity condition may also be imposed.

Defined by [BCD+89], who also showed that SAC_k is closed under complement for every k>0.

Linked From

SAC⁰: Semi-Unbounded-Fanin AC⁰

See SAC for definition.

Not closed under complement [BCD+89].

Not contained in ⊕SAC⁰ [K23].

SAC¹: Semi-Unbounded-Fanin AC¹

See SAC for definition.

Equals LOGCFL/poly [Ven91].

Contained in ⊕SAC¹ [GW96].

More about...