Class Description

RNC: Randomized NC

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.

Linked From

coRNC: Complement of RNC

Contains the problem of whether a bipartite graph has a perfect matching [Kar86].

More about...


NC: Nick's Class

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

More about...


QNC: Quantum NC

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.

More about...


RNC1: Randomized NC1

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.

More about...


ZP•L: Zero-Error Probabilistic L with Two Way Access to Randomness

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

Contains BPL [Nis93].

Contained in RNC since L is contained in NC and zero sided error is weaker than one sided error.

Contained in BP•L.

More about...