By definition, a decision problem in NC0 can depend on only a constant number of bits of the input. Thus, NC0 usually refers to functions computable by constant-depth, bounded-fanin circuits.
There is a family of permutations computable by a uniform family of NC0 circuits that is P-hard to invert [Has88].
Recently [AIK04] solved a longstanding open problem by showing that there exist pseudorandom generators and one-way functions in NC0, based on (for example) the hardness of factoring. Specifically, in these generators every bit of the output depends on only 4 input bits. Whether the dependence can be reduced to 3 bits under the same cryptographic assumptions is open, but [AIK04] have some partial results in this direction. It is known that the dependence cannot be reduced to 2 bits.
An especially important subclass of AC, corresponding to constant-depth, unbounded-fanin, polynomial-size circuits with AND, OR, and NOT gates.
Computing the Parity or Majority of n bits is not in AC0 [FSS84].
There are functions in AC0 that are pseudorandom for all statistical tests in AC0 [NW94]. But there are no functions in AC0 that are pseudorandom for all statistical tests in QP (quasipolynomial time) [LMN93].
[LMN93] showed furthermore that functions with AC0 circuits of depth d are learnable in QP, given their outputs on O(2log(n)^O(d)) randomly chosen inputs. On the other hand, this learning algorithm is essentially optimal, unless there is a 2n^o(1) algorithm for factoring [Kha93].
Although there are no good pseudorandom functions in AC0, [IN96] showed that there are pseudorandom generators that stretch n bits to n+Θ(log n), assuming the hardness of a problem based on subset sum.
AC0 contains NC0, and is contained in QACf0 and MAC0.
In descriptive complexity, uniform AC0 can be characterized as the class of problems expressible by first-order predicates with addition and multiplication operators - or indeed, with ordering and multiplication, or ordering and division (see [Lee02]). So it's equivalent to the class FO, and to the alternating logtime hierarchy.
[BLM+98] showed the following problem is complete for depth-k AC0 circuits (with a uniformity condition):
Constant-depth quantum circuits without fanout gates.
Defined in [Spa02].
Contained in QNCf0.
Constant-depth quantum circuits with bounded fan-in, with polynomial size quantum advice. Contains QNC0 and QNC0/🐱
Constant-depth quantum circuits without fanout gates, with an additional cat state as "advice": 🐱 = .
Defined in [WKST19].
Contains QNC0. Contained in QNC0/qpoly and BQP.
Constant-depth quantum circuits with unbounded-fanout gates.
Defined in [Spa02].
Contains QNC0, and is contained in QACC0.Is equivalent to QACf0 due to [Tak12].
