AC0

AC0 is a complexity class in circuit complexity, a branch of complexity theory. It contains all the functions that (1) and polynomial size with AND gates and OR gates with unbounded fan-in, and possibly non- gates can be calculated at the inputs of circuit families with depth O. It is the smallest class in the AC hierarchy and is above NC0 which only allows gates with limited fan-in.

In the descriptive complexity theory corresponds DLOGTIME - uniform AC0 descriptive class FO BIT of languages ​​that can be described in first-order logic with the BIT operator, the class FO ( , ), and the logarithmic hierarchy.

1984 showed Furst, Saxe and Sipser that the parity function is not in AC0. It follows that the function is not in Majority AC0. Consequently, AC0 is equal NC1. Addition and subtraction of whole numbers are in AC0, multiplication, however, not (at least with the usual representations in base 2 or 10).