ACi is the class of decision problems solvable by a nonuniform family of Boolean circuits, with polynomial size, depth O(logi(n)), and unbounded fanin. The gates allowed are AND, OR, and NOT.
Then AC is the union of ACi over all nonnegative i.
ACi is contained in NCi+1; thus, AC = NC.
For a random oracle A, (ACi)A is strictly contained in (ACi+1)A, and (uniform) ACA is strictly contained in PA, with probability 1 [Mil92].
FO-uniform AC with depth is equal to FO[].
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):
See AC for definition.
Contains NL (hence also NC1). Contained in NC2. The complexity class DET also obeys all these containment relationships, but no containment is known in either direction between AC1 and DET.
The class of decision problems solvable by a uniform family of polynomial-size, unbounded-fanin, depth O(log log n) circuits with AND, OR, and NOT gates. Equals FO(log log n).
Defined in [BKL+00], where it was also shown that many problems on finite groups are in FOLL.
Contains uniform AC0, and is contained in uniform AC1.
Is not known to be comparable to L or NL.
(Named in honor of Nick Pippenger.)
NCi is the class of decision problems solvable by a uniform family of Boolean circuits, with polynomial size, depth O(logi(n)), and fan-in 2.
Then NC is the union of NCi over all nonnegative i.
Also, NC equals the union of PT/WK(logkn, nk)/poly over all constants k.
NCi is contained in ACi; thus, NC = AC.
Contains NL, in fact NL is contained in NC2.
Generalizations include RNC and QNC.
[IN96] construct a candidate pseudorandom generator in NC based on the subset sum problem.
For a random oracle A, (NCi)A is strictly contained in (NCi+1)A, and uniform NCA is strictly contained in PA, with probability 1 [Mil92].
In descriptive complexity, NC can be defined by FO[]
Log space uniform NC is contained in ATIME(poly(log(n))) = polyL [RUZ81].
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.
TCi is the class of decision problems solvable by polynomial-size, depth circuits with unbounded fanin AND, OR, and majority (MAJ) gates. A majority gate returns 1 if at least half of its inputs are 1, and 0 otherwise. Other gates that can be used in place of majority (up to polynomial size equivalence) are threshold gates (THR) and MODpn, where pn is the nth prime.
A uniformity requirement is sometimes also placed.
Each TCi contains ACi (in fact ACCi) and is contained in NCi+1. Thus NC = AC = TC.
