Class Description

SAC: Semi-Unbounded-Fanin AC

SACk is the class of decision problems solvable by a family of depth-O(logkn) 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 SACk is closed under complement for every k>0.

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