Class Description

NC2: Level 2 of NC

See NC for definition.

Contains AC1 and DET, both of which contain NL. It seems we currently (as of this writing, 15 Jun 2022) do not know any problem in NC2 that's not known to be in AC1DET (see this question).

Linked From

AC1: Unbounded Fanin Log-Depth Circuits

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.

More about...


BPL: Bounded-Error Probabilistic L

Has the same relation to L as BPP does to P. The Turing machine has to halt for every input and every randomness.

The randomness is read once. That is, each random bit is only given once and to be referenced again it must be stored in the working space. This in contrast to the two way randomness of BP•L.

Contained in SC [Nis92], PL, BP•L, ZP•L [Nis93], DET [Coo85], NC2 and P [BCP83].

More about...


DET: Determinant

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.

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


NL: Nondeterministic Logarithmic-Space

NL is to L as NP is to P. Not known whether a particular relation (equality or inequality) between P and NP implies the same relation between L and NL.

In a breakthrough result, was shown to equal coNL [Imm88] [Sze87]. (Though contrast to mNL.)

Is contained in LOGCFL [Sud78], as well as NC2.

Is contained in UL/poly [RA00].

Deciding whether a bipartite graph has a perfect matching is hard for NL [KUW86].

NL can be defined in a logical formalism as SO(krom) and also as FO(tc), reachability in directed graph is NL-Complete under FO-reduction.

More about...


VNPk: Valiant NP Over Field k

A superclass of VPk in Valiant's algebraic complexity theory, but not quite the analogue of NP.

A problem is in VNPk if there exists a polynomial p with the following properties:

Originated in [Val79b].

If the field k has characteristic greater than 2, then the permanent of an n-by-n matrix of indeterminates is VNPk-complete under a type of reduction called p-projections ([Val79b]; see also [Bur00]).

A central conjecture is that for all k, VPk is not equal to VNPk. Bürgisser [Bur00] shows that if this were false then:

In both cases, PH collapses to Σ2P.

More about...