Nick's Class

From dankwiki
Revision as of 13:41, 12 May 2013 by Dank (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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(lgc n) using O(nk) parallel processors.

(Named after Nick Pippinger, not me.)