1AC0

1AC0 is a restricted circuit complexity class related to the broader AC0 family. In some literature it is described as the depth-1 fragment of AC0, consisting of Boolean functions computable by circuits of constant depth equal to one. The defining feature is that the circuit has a single gate at the output, with inputs drawn from the input variables (possibly negated) and allowed unbounded fan-in. Accordingly, 1AC0 captures functions that can be expressed as either an AND of a set of literals or an OR of a set of literals, with the constants 0 and 1 included as degenerate cases when the set is empty.

Concretely, a 1AC0 circuit computes either the conjunction of a (possibly empty) collection of literals x_i or ¬x_i, or the disjunction of a (possibly empty) collection of literals, depending on whether the single gate is an AND or an OR. This makes 1AC0 a very small, highly structured subclass of AC0, and it is strictly weaker than AC0 for all sufficiently large input sizes.

Relation to other classes: 1AC0 is contained within AC0, since AC0 allows deeper constant-depth circuits with the same unbounded fan-in gates, but these depth-1 circuits cannot express the more complex boolean functions that require additional layers. Because of its depth restriction, 1AC0 is incapable of computing many functions that AC0 can handle. It is primarily of theoretical interest as a baseline for comparing circuit hierarchies and for illustrating the consequences of depth constraints in constant-depth circuit classes.

Examples of computable functions in 1AC0 include the constant functions 0 and 1, a single literal or its negation, and the overall AND or OR over a set of literals. See also AC0, circuit complexity, boolean function, and literals.