Class Description

TC: Threshold Circuits

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.

Linked From

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.

More about...


TC1: Log-depth Threshold Circuits

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

More about...