Nick's Class

Steven Cook's class of those problems decidable in polylogarithmic time on polynomially many processors. A problem is in NC if there exist constants c and k such that it can be solved in time O(lg^c n) using O(n^k) parallel processors.

(Named after Nick Pippinger, not me.)