Has the same relation to NC as RP does to P.
Contains the maximum matching problem for bipartite graphs [MVV87].
Contained in QNC.
See also: coRNC.
Contains the problem of whether a bipartite graph has a perfect matching [Kar86].
(Named in honor of Nick Pippenger.)
NCi is the class of decision problems solvable by a uniform family of Boolean circuits, with polynomial size, depth O(logi(n)), and fan-in 2.
Then NC is the union of NCi over all nonnegative i.
Also, NC equals the union of PT/WK(logkn, nk)/poly over all constants k.
NCi is contained in ACi; thus, NC = AC.
Contains NL, in fact NL is contained in NC2.
Generalizations include RNC and QNC.
[IN96] construct a candidate pseudorandom generator in NC based on the subset sum problem.
For a random oracle A, (NCi)A is strictly contained in (NCi+1)A, and uniform NCA is strictly contained in PA, with probability 1 [Mil92].
In descriptive complexity, NC can be defined by FO[]
Log space uniform NC is contained in ATIME(poly(log(n))) = polyL [RUZ81].
The class of decision problems solvable by polylogarithmic-depth quantum circuits with bounded probability of error. (A uniformity condition may also be imposed.)
Has the same relation to NC as BQP does to P.
[CW00] showed that factoring is in ZPP with a QNC oracle.
Is incomparable with BPP as far as anyone knows.
See also: RNC.
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.
Has the same relationship to BP•L as ZPP has to BPP. More specifically, the set of languages with a log space, polynomial time Turing machine using a read only randomness tape such that on input x:
1. With high probability over the random bits used in the randomness tape will the machine correctly output whether x is in the language.
2. The machine will either wither correctly output whether x is in the language, or output 'unknown'.
Contained in RNC since L is contained in NC and zero sided error is weaker than one sided error.
Contained in BP•L.
