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.
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.
See TC for definition.
In addition to the different gatesets allowed in place of AND, OR, THR, also equivalent to arithmetic/counting analogue of AC1 modulo pn (the nth prime) [RT92].
