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.)
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].
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].
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.
ALOGTIME is the class of languages decidable in logarithmic time by a random access alternating Turing machine.
Known to be equal to UE*-uniform NC1.
Languages decided with two sided bounded error by a log space machine with a read only tape containing random bits. In contrast with BPL, the random bits can be read multiple times without storing them in working space.
For example, BP•L contains RNC1 since NC1 is contained in L. However, this reduction does not hold for BPL.
It is unknown if BP•L is contained in P [Nis93].
Contained in BPP.
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.
Roughly, the class of continuous problems solvable by an ordinary differential equation (ODE) with convergence time logarithmic in the size of the input. The vector field of the ODE is specified by an NC1 formula, with n parameters that represent the input. The point to which the ODE converges (assuming it does) is the output.
Defined in [BSF02], which should be consulted for more details.
[BSF02] show that finding the maximum of n integers is in CLOG. Thus, CLOG is best thought of as the continuous-time analog of NC1, not of DTIME(log n).
Contained in CP.
The class of decision problems reducible in L to the problem of computing the determinant of an n-by-n matrix of n-bit integers.
Defined in [Coo85]. (Cook used NC1 reductions in his definition)
Contained in NC2, and contains NL and PL [BCP83].
Graph isomorphism is hard for DET under L-reductions [Tor00].
The corresponding function class turns out to be equal to GapL (see refs at GapL), that is, the determinant of integer matrices is GapL-complete.
See k-PBP for the definition of a classical branching program.
A quantum branching program is the natural quantum generalization: we have a quantum state in a Hilbert space of dimension k. Each step t consists of applying a unitary matrix U(t)(xi): that is, U(t) depends on a single bit xi of the input. (So these are the quantum analogues of so-called oblivious branching programs.) In the end we measure to decide whether to accept; there must be zero probability of error.
Defined in [AMP02], where it was also shown that NC1 is contained in 2-EQBP.
k-BQBP can be defined similarly.
The class of decision problems solvable by a Turing machine restricted to use an amount of memory logarithmic in the size of the input, n. (The input itself is not counted as part of the memory.)
L is contained in P. L contains NC1 [Bor77], and is contained in generalizations including NL, L/poly, SL, RL, ⊕L, and ModkL.
Reingold [Rei04] showed that, remarkably, L = SL. In other words, undirected graph connectivity is solvable in deterministic logarithmic space.
Immerman [Imm83] showed that L is the class FO(dtc) of first-order expressible queries with a deterministic transitive closure.
L queries are exactly the one that can be written in a syntactic restriction of While languages.
The class of decision problems solvable by a family of monotone NC1 circuits (i.e. AND and OR gates only).
A uniformity condition could also be imposed.
Defined in [GS90].
Strictly contained in mNL [KW88], and indeed in mL [GS91].
Strictly contains mTC0 [Yao89].
A branching program is a directed acyclic graph with a designated start vertex. Each (non-sink) vertex is labeled by the name of an input bit, and has two outgoing edges, one of which is followed if that input bit is 0, the other if the bit is 1. A sink vertex can be either an 'accept' or a 'reject' vertex.
The size of the branching program is the number of vertices. The branching program has width k if the vertices can be sorted into levels, each with at most k vertices, such that each edge goes from a level to the one immediately after it.
Then k-PBP is the class of decision problems solvable by a family of polynomial-size, width-k branching programs. (A uniformity condition may also be imposed.)
k-PBP equals (nonuniform) NC1 for constant k at least 5 [Bar89]. On the other hand, 4-PBP is in ACC0 [BT88].
Contained in k-EQBP, as well as PBP.
See also BPd(P).
Same as QNC, but logarithmic depth instead of polylogarithmic depth.
At one point, this wiki incorrectly said that it was QNC but with exact answers instead of bounded error; this was probably someone's confusion with classes like QCMA1 vs QCMA and QMA1 vs QMA. In theory this could be QNC1, but such a class does not seem to appear in the literature (yet)!
In contrast to NC1, it is not clear how to simulate QNC1 on a quantum computer in which one qubit is initialized to a pure state, and the remaining qubits are in the maximally mixed state [ASV00].
See also [MN02].
The class of decision problems solvable by deterministic finite automata (DFAs).
Equals the class solvable by nondeterministic finite automata (NDFAs).
Equals DSPACE(O(1)) [She59], which equals DSPACE(o(log log n)) [HLS65].
Includes, i.e., "Is the parity of the input odd?," but not "Are the majority of bits in the input 1's?" This is sometimes expressed as "finite automata can't count."
Contained in NC1.
See e.g. [Koz97], [Gur89] for basic results on regular languages.
Has the same relation to RNC as NC1 does to NC. And the same relation to NC1 as RP does to P.
Contained in BP•L.
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.