Class Description

polyL: Polylogarithmic Space

Equals DSPACE((log n)^c).

In contrast to L, which is contained in P, it is not known if polyL is contained in P or vice versa (or if none of the inclusions hold). On the other hand, we do know that polyL does not equal P, since (for example) polyL does not have complete problems under many-to-one logspace reductions.

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