Class Description

NC²: Level 2 of NC

See NC for definition.

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

Linked From

AC¹: Unbounded Fanin Log-Depth Circuits

See AC for definition.

Contains NL (hence also NC¹). Contained in NC². The complexity class DET also obeys all these containment relationships, but no containment is known in either direction between AC¹ 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], NC² 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 NC¹ reductions in his definition)

Contained in NC², 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.)

NCⁱ is the class of decision problems solvable by a uniform family of Boolean circuits, with polynomial size, depth O(logⁱ(n)), and fan-in 2.

Then NC is the union of NCⁱ over all nonnegative i.

Also, NC equals the union of PT/WK(log^kn, n^k)/poly over all constants k.

NCⁱ is contained in ACⁱ; thus, NC = AC.

Contains NL, in fact NL is contained in NC².

Generalizations include RNC and QNC.

[IN96] construct a candidate pseudorandom generator in NC based on the subset sum problem.

For a random oracle A, (NCⁱ)^A is strictly contained in (NCⁱ⁺¹)^A, and uniform NC^A is strictly contained in P^A, with probability 1 [Mil92].

In descriptive complexity, NC can be defined by FO[${\displaystyle \log(n)^{O(1)}}$]

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

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

VNP_k: Valiant NP Over Field k

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

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

• p is computable in VP_k; that is, by a polynomial-size straight-line program.
• The inputs to p are constants c₁,...,c_m,e₁,...,e_h and indeterminates X₁,...,X_n over the base field k.
• When p is summed over all 2^h possible assignments of {0,1} to each of e₁,...,e_h, the result is some specified polynomial q.

Originated in [Val79b].

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

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

• If k is finite, NC²/poly = P/poly = NP/poly = PH/poly.
• If k has characteristic 0, then assuming the Generalized Riemann Hypothesis (GRH), NC³/poly = P/poly = NP/poly = PH/poly, and #P/poly = FP/poly.

In both cases, PH collapses to Σ₂P.

More about...