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):
The class of functions from {0,1}n to nonnegative integers computed by polynomial-size constant-depth arithmetic circuits, using addition and multiplication gates and the constants 0 and 1.
Contained in GapAC0.
Same as AC0, but now "MOD m" gates (for a specific m) are allowed in addition to AND, OR, and NOT gates. (A MOD m gate outputs 0 if the sum of its inputs is congruent to 0 modulo m, and 1 otherwise.)
If m is a power of a prime p, then for any prime q not equal to p, deciding whether the sum of n bits is congruent to 0 modulo q is not in AC0[m] [Raz87] [Smo87]. It follows that, for any such m, AC0[m] is strictly contained in NC1.
However, if m is a product of distinct primes (e.g. 6), then it is not even known whether AC0[m] = NP!
See also: QAC0[m].
Same as AC0[m], but now the constant-depth circuit can contain MOD m gates for any m.
Contained in TC0.
Indeed, can be simulated by depth-3 threshold circuits of quasipolynomial size [Yao90].
According to [All96], there is no good evidence for the existence of cryptographically secure functions in ACC0.
There is no non-uniform ACC0 circuits of polynomial size for NTIMES[2n] and no ACC0 circuit of size 2nO(1) for ENP (The class E with an NP oracle). These are the only two known nontrivial lower bounds against ACC0 and were recently discovered by [Wil11].
The class of problems for which there exists a DiffAC0 function f such that the answer is "yes" on input x if and only if f(x)=0.
Equals TC0 and PAC0 under logspace uniformity [ABL98].
The set of problems solvable by by constant-depth circuits having only MODm gates for constant .
It was shown in [CW22] that any symmetric function can be computed by depth-3 CC0 circuits with size 2O(na) for any constant a. Such a circuit uses a modulus m with size at most (1/a)2/a.
This is in contrast with AC0 which requires size 2O(n1/(d-1)) for depth d circuits computing arbitrary symmetric functions [Has87]. Even AC0[m] for prime power m requires size 2O(n1/(2d)) for depth d [Raz87] [Smo87].
Same as Dyn-FO, except that now updates are computed via constant-depth predicates that have "COUNT" available, in addition to AND, OR, and NOT -- so it's a uniform version of TC0 rather than of AC0.
See [HI02] for more information.
First order logic is the smallest logical class of logic language. It is the base of Descriptive complexity and equal to the class AC0.
When we use logic formalism, the input is a structure, usually it is either strings (of bits or over an alphabet) whose elements are position of the strings, or graphs whose elements are vertices. The measure of the input will there be the size of the structure.Whatever the structure is, we can suppose that there are relation that you can test, by example is true iff there is an edge from to if the structure is a graph, and is true iff the nth letter of the string is 1. We also have constant, who are special elements of the structure, by example if we want to check reachability in a graph, we will have to choose two constant s and t.
In descriptive complexity we almost always suppose that there is a total order over the elements and that we can check equality between elements. This let us consider elements as number, is the number iff there is elements such that . Thanks to this we also want the primitive "bit", where is true if only the th bit of is 1. (We can replace by plus and time, ternary relation such that is true iff and is true iff ).
Since in a computer elements are only pointers or string of bits, those assumptions make sense, and those primitive functions can be calculated in most of the small complexity classes. We can also imagine FO without those primitives, which gives us smaller complexity classes.
The language FO is then defined as the closure by conjunction ( ), negation () and universal quantification () over element of the structures. We also often use existential quantification () and disjunction () but those can be defined thanks to the 3 first symbols.
The semantics of the formulae in FO is straightforward, is true iff is false, is true iff is true and is true, and () is true iff whatever element we decide that is we can choose, is true.
A query in FO will then be to check if a FO formulae is true over a given structure, this structure is the input of the problem. One should not confuse this kind of problem with checking if a quantified boolean formula is true, which is the definition of QBF, which is PSPACE-complete. The difference between those two problem is that in QBF the size of the problem is the size of the formula and elements are just boolean value, whereas in FO the size of the problem is the size of the structure and the formula is fixed.
Every formulae is equivalent to a formulae in prenex normal form where we put recursively every quantifier and then a quantifier-free formulae.
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.
The class of decision problems solvable by a nonuniform family of Boolean circuits, with a linear number of gates, constant depth and unbounded fanin. Not to be confused with WLC0, which has a linear number of wires.
It is properly contained in AC0 [CR96].
Same as AC0, except now we're allowed a single unbounded-fanin majority gate at the root.
Defined in [JKS02].
MAC0 is strictly contained in TC0 [ABF+94].
The Political Action Committee for computational complexity research.
The class of problems for which there exists a DiffAC0 function f such that the answer is "yes" on input x if and only if f(x)>0.
Equals TC0 and C=AC0 under logspace uniformity [ABL98].
The class of decision problems solvable by a family of constant-depth, polynomial-size quantum circuits. Here each layer of the circuit is a tensor product of one-qubit gates and Toffoli gates, or is a tensor product of controlled-NOT gates.
A uniformity condition may also be imposed.
Defined in [Moo99].
It is contained in QACf0, but it is not known if it contains AC0. Notice that the latter containment is not obvious, since the set of gates in QAC0 do not allow to implement fanout in any way we may take for granted.
See SAC for definition.
Not closed under complement [BCD+89].
Not contained in ⊕SAC0 [K23].
See SAC for definition.
See TC for definition.
TC0 contains ACC0, and is contained in NC1.
TC0 circuits of depth 3 are strictly more powerful than TC0 circuits of depth 2 [HMP+93].
TC0 circuits of depth 3 and quasipolynomial size can simulate all of ACC0 [Yao90].
There is a function in AC0 (explicitly given in [She08]), whose computation with TC0 circuits of depth 2 requires an exponential number of gates.
[NR97] give a candidate pseudorandom function family computable in TC0, that is secure assuming a subexponential lower bound on the hardness of factoring. (See also [NRR01] for an improvement of this construction, as well as [Kha93].)
One implication is that, assuming such a bound, there is no natural proof in the sense of [RR97] separating TC0 from P/poly. (It is important for this that a function family, and not just a candidate pseudorandom generator, is computable in TC0.) Another implication is that functions in TC0 are likely to be difficult to learn.
The permanent of a 0-1 matrix cannot be computed in uniform TC0 [All99].
In a breakthrough result [Hes01] (building on [BCH86] and [CDL01]), integer division was shown to be in UD-uniform TC0. Indeed division is complete for this class under AC0 reductions.
The class of decision problems solvable by a nonuniform family of Boolean circuits, with a linear number of wires, constant depth and unbounded fanin. Contained in LC0, and therefore strictly contained in AC0.
