Class Description

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.

Linked From

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