AC0

Descriptive complexity

From a descriptive complexity viewpoint, DLOGTIME-uniform AC⁰ is equal to the descriptive class FO+BIT of all languages describable in first-order logic with the addition of the BIT predicate, or alternatively by FO(+, ×), or by Turing machine in the logarithmic hierarchy.

Separations

In 1984 Furst, Saxe, and Sipser showed that calculating the PARITY of the input bits (unlike the aforementioned addition/subtraction problems above which had two inputs) cannot be decided by any AC⁰ circuits, even with non-uniformity. Similarly, computing the majority is also not in ${\displaystyle {\mathsf{A}\mathsf{C}}^0}$. It follows that AC⁰ is strictly smaller than TC⁰. Note that "PARITY" is also called "XOR" in the literature.

However, PARITY is only barely out of AC⁰, in the sense that for any ${\displaystyle k>0}$, there exists a family of alternating circuits using depth ${\displaystyle \lceil k\ln n/\ln \ln n\rceil }$ and size ${\displaystyle O\left(2^{(\ln n{)}^{1/k}}\frac{n}{(\ln n{)}^{1/k}}\right)}$. In particular, setting ${\displaystyle k}$ to be a large constant, then there exists a family of alternating circuits using depth ${\displaystyle O(\ln n/\ln \ln n)\ll O(\ln n)}$, and size only slightly superlinear.

${\displaystyle {\mathsf{A}\mathsf{C}}^0}$ can be divided further, into a hierarchy of languages requiring up to 1 layer, 2 layers, etc. Let ${\displaystyle {\mathsf{A}\mathsf{C}}_d^0}$ be the class of languages decidable by a threshold circuit family of up to depth ${\displaystyle d}$:$${\displaystyle {\mathsf{A}\mathsf{C}}_1^0\subset {\mathsf{A}\mathsf{C}}_2^0\subset \cdots \subset {\mathsf{A}\mathsf{C}}^0=\bigcup _{d=1}^{\mathrm{\infty }}{\mathsf{A}\mathsf{C}}_d^0}$$The following problem is ${\displaystyle {\mathsf{A}\mathsf{C}}_d^0}$-complete under a uniformity condition: given a grid graph of polynomial length and width ${\displaystyle d}$, decide whether two given vertices are connected.

The addition of two ${\displaystyle n}$-bit integers is in ${\displaystyle {\mathsf{A}\mathsf{C}}_3^0}$ but not in ${\displaystyle {\mathsf{A}\mathsf{C}}_2^0}$.