Class Description

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

Linked From

AC: Unbounded Fanin Polylogarithmic-Depth Circuits

ACi is the class of decision problems solvable by a nonuniform family of Boolean circuits, with polynomial size, depth O(logi(n)), and unbounded fanin. The gates allowed are AND, OR, and NOT.

Then AC is the union of ACi over all nonnegative i.

ACi is contained in NCi+1; thus, AC = NC.

AC1 contains NL.

For a random oracle A, (ACi)A is strictly contained in (ACi+1)A, and (uniform) ACA is strictly contained in PA, with probability 1 [Mil92].

FO-uniform AC with depth is equal to FO[].

More about...


CC: Comparator Circuits

A comparator gate consists of two inputs and outputs the minimum of its two inputs on its first output wire and outputs the maximum of its two inputs on its second output wire. One important restriction is that each output of a comparator gate has fanout at most one. The Comparator Circuit Value Problem (CCVP) is defined as following. Given a circuit composed of comparator gates, the inputs to the circuit, and one output of the circuit, calculate the value of this output.

CC is defined as the class of problems log-space many-one reducible to CCVP [MS89]. At present it is only known that NLCCP [MS89]. CC is an example of a complexity class neither known to be in NC nor P-complete.

Natural complete problems for the CC class include Stable Marriage Problem, Stable Roommate Problem, Lex-first Maximal Matching [Sub94].

More about...


FO[]: Iterated First-Order logic

Let be a function from integers to integers. abbreviates and abbreviates .

A quantifier block is a list where the s are quantifier free FO-formulae and each s is either or .If is a quantifier block then is the block consisting of iterated copies of . Note that there are quantifiers in the list, but only k variables; each variable is used times.

FO[] consists of the FO-formulae with quantifier blocks that are iterated times.

In Descriptive complexity we can see that :

More about...


NC0: Level 0 of NC

By definition, a decision problem in NC0 can depend on only a constant number of bits of the input. Thus, NC0 usually refers to functions computable by constant-depth, bounded-fanin circuits.

There is a family of permutations computable by a uniform family of NC0 circuits that is P-hard to invert [Has88].

Recently [AIK04] solved a longstanding open problem by showing that there exist pseudorandom generators and one-way functions in NC0, based on (for example) the hardness of factoring. Specifically, in these generators every bit of the output depends on only 4 input bits. Whether the dependence can be reduced to 3 bits under the same cryptographic assumptions is open, but [AIK04] have some partial results in this direction. It is known that the dependence cannot be reduced to 2 bits.

More about...


NC1: Level 1 of NC

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

Is contained in L [Bor77].

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

More about...


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

More about...


P: Polynomial-Time

The class that started it all.

The class of decision problems solvable in polynomial time by a Turing machine. (See also FP, for function problems.)

Defined in [Edm65], [Cob64], [Rab60], and other seminal early papers.

Contains some highly nontrivial problems, including linear programming [Kha79] and finding a maximum matching in a general graph [Edm65].

Contains the problem of testing whether an integer is prime [AKS02], an important result that improved on a proof requiring an assumption of the generalized Riemann hypothesis [Mil76].

A decision problem is P-complete if it is in P, and if every problem in P can be reduced to it in L (logarithmic space). The canonical P-complete problem is circuit evaluation: given a Boolean circuit and an input, decide what the circuit outputs when given the input.

Important subclasses of P include L, NL, NC, and SC.

P is contained in NP, but whether they're equal seemed to be an open problem when I last checked.

Efforts to generalize P resulted in BPP and BQP.

The nonuniform version is P/poly, the monotone version is mP, and versions over the real and complex number fields are PR and PC respectively.

In descriptive complexity, P can be defined by three different kind of formulae, FO(lfp) which is also FO()], and also as SO(Horn)

P queries are exactly the one that can be written in the While/cons languages.

P is the class of decision problems solvable by a (logspace) uniform family of polynomial-size Boolean circuits.

P can be computed by interactive protocols (see IP) where the verifier runs in log space (see L and BPL) [GKR15].

More about...


PT/WK(f(n),g(n)): Parallel Time f(n) / Work g(n)

The class of decision problems solvable by a uniform family of Boolean circuits with depth upper-bounded by f(n) and size (number of gates) upper-bounded by g(n).

The union of PT/WK(logkn, nk) over all constants k equals NC.

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


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.

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


TC: Threshold Circuits

TCi is the class of decision problems solvable by polynomial-size, depth circuits with unbounded fanin AND, OR, and majority (MAJ) gates. A majority gate returns 1 if at least half of its inputs are 1, and 0 otherwise. Other gates that can be used in place of majority (up to polynomial size equivalence) are threshold gates (THR) and MODpn, where pn is the nth prime.

A uniformity requirement is sometimes also placed.

Each TCi contains ACi (in fact ACCi) and is contained in NCi+1. Thus NC = AC = TC.

More about...


VNCk: Valiant NC Over Field k

Has the same relation to VPk as NC does to P.

More formally, the class of VPk problems computable by a straight-line program of depth polylogarithmic in n.

Surprisingly, VNCk = VPk for any k [VSB+83].

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


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