Class Description

TC0: Constant-Depth Threshold Circuits

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.

Linked From

ACC0: AC0 With Arbitrary MOD Gates

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].

Contains 4-PBP [BT88].

See also: QACC0 and CC0.

More about...


C=AC0: Exact-Counting AC0

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].

More about...


CH: Counting Hierarchy

The union of the CkP's over all constant k.

Contained in PSPACE.

Strictly contains DLOGTIME-uniform TC0 [CMTV98].

It is an open problem whether there exists an oracle relative to which CH is infinite, or even unequal to PSPACE. This is closely related to the problem of whether TC0 = NC1, since a padding argument shows that TC0 = NC1 implies CH = PSPACE.

More about...


Dyn-ThC0: Dynamic Threshold Circuits

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.

More about...


K: Feasibly recursive functions

A class of number-theoretic functions, defined as the closure of basic integer arithmetic operations (, as well as constants 0, 1, and projections) under composition and polynomially long sums and products. Defined by [Con73], who mistakenly claimed it coincides with FP.

Equals UD-uniform FTC0 by [Hes01].

More about...


MAC0: Majority of AC0

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].

More about...


mTC0: Monotone TC0

The class of decision problems solvable by a family of monotone TC0 circuits (i.e. constant-depth, polynomial-size, AND, OR, and threshold gates, but no NOT gates).

A uniformity condition could also be imposed.

Defined in [GS90].

Strictly contained in mNC1 [Yao89].

More about...


NC1: Level 1 of NC

See NC for definition.

[KV94] give a family of functions that is computable in NC1, but not efficiently learnable unless there exists an efficient algorithm for factoring Blum integers.

Was shown to equal 5-PBP [Bar89]. On the other hand, width 5 is necessary unless NC1 = ACC0 [BT88].

As an application of this result, NC1 can be simulated on a quantum computer with three qubits, one initialized to a pure state and the remaining two in the maximally mixed state [ASV00]. Surprisingly, [AMP02] showed that only a single qubit is needed to simulate NC1 - i.e. that NC1 is contained in 2-EQBP. (Complex amplitudes are needed for this result.)

Is contained in L [Bor77].

Contains TC0.

NC1 contains the integer division problem [BCH86], even if an L-uniformity condition is imposed [CDL01].

UE*-uniform NC1 is equal to ALOGTIME [RUZ81].

More about...


PAC0: Probabilistic AC0

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].

More about...