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(log^kn, n^k) over all constants k equals NC.

Linked From

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