Class Description

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

Linked From

AC: Unbounded Fanin Polylogarithmic-Depth Circuits

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

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

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

AC¹ contains NL.

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

FO-uniform AC with depth ${\displaystyle t(n)}$ is equal to FO[${\displaystyle t(n)}$].

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 NL${\displaystyle \subseteq }$CC${\displaystyle \subseteq }$P [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[${\displaystyle t(n)}$]: Iterated First-Order logic

Let ${\displaystyle t(n)}$ be a function from integers to integers.${\displaystyle (\forall xP)Q}$ abbreviates ${\displaystyle (\forall x(P\Rightarrow Q))}$ and ${\displaystyle (\exists xP)Q}$ abbreviates ${\displaystyle (\exists x(P\wedge Q))}$.

A quantifier block is a list ${\displaystyle (Q_{1}x_{1}.\phi _{1})...(Q_{k}x_{k}.\phi _{k})}$ where the ${\displaystyle \phi _{i}}$s are quantifier free FO-formulae and each ${\displaystyle Q_{i}}$s is either ${\displaystyle \forall }$ or ${\displaystyle \exists }$.If ${\displaystyle Q}$ is a quantifier block then ${\displaystyle [Q]^{t(n)}}$ is the block consisting of ${\displaystyle t(n)}$ iterated copies of ${\displaystyle Q}$. Note that there are ${\displaystyle k*t(n)}$ quantifiers in the list, but only k variables; each variable is used ${\displaystyle t(n)}$ times.

FO[${\displaystyle t(n)}$] consists of the FO-formulae with quantifier blocks that are iterated ${\displaystyle \Theta (t(n))}$ times.

In Descriptive complexity we can see that :

• FO[${\displaystyle (\log n)^{i}}$] is equal to fo-uniform ACⁱ, and in fact FO[${\displaystyle t(n)}$] is fo-uniform AC of depth ${\displaystyle t(n)}$
• FO[${\displaystyle (\log n)^{O(1)}}$] is equal to NC
• FO[${\displaystyle n^{O(1)}}$] is equal to P and FO(LFP)
• FO[${\displaystyle 2^{n^{O(1)}}}$] is equal to PSPACE and FO(PFP)

More about...

NC⁰: Level 0 of NC

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

There is a family of permutations computable by a uniform family of NC⁰ 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 NC⁰, 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...

NC¹: Level 1 of NC

See NC for definition.

[KV94] give a family of functions that is computable in NC¹, 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 NC¹ = ACC⁰ [BT88].

As an application of this result, NC¹ 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 NC¹ - i.e. that NC¹ is contained in 2-EQBP. (Complex amplitudes are needed for this result.)

Is contained in L [Bor77].

Contains TC⁰.

NC¹ contains the integer division problem [BCH86], even if an L-uniformity condition is imposed [CDL01].

U_E^*-uniform NC¹ is equal to ALOGTIME [RUZ81].

More about...

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

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 P_R and P_C respectively.

In descriptive complexity, P can be defined by three different kind of formulae, FO(lfp) which is also FO(${\displaystyle n^{O(1)}}$)], 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(log^kn, n^k) 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...

RNC¹: Randomized NC1

Has the same relation to RNC as NC¹ does to NC. And the same relation to NC¹ as RP does to P.

Contained in BP•L.

More about...

TC: Threshold Circuits

TCⁱ is the class of decision problems solvable by polynomial-size, depth ${\displaystyle O(\log ^{i}n)}$ 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 MOD_pn, where p_n is the nth prime.

A uniformity requirement is sometimes also placed.

Each TCⁱ contains ACⁱ (in fact ACCⁱ) and is contained in NCⁱ⁺¹. Thus NC = AC = TC.

More about...

VNC_k: Valiant NC Over Field k

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

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

Surprisingly, VNC_k = VP_k for any k [VSB+83].

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

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