Check out my first novel, midnight's simulacra!

Nick's Class: Difference between revisions

From dankwiki
(Created page with 'CATEGORY: Computer Science Eponyms')
 
No edit summary
 
(One intermediate revision by the same user not shown)
Line 1: Line 1:
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<sup>c</sup> n) using O(n<sup>k</sup>) parallel processors.
(Named after [http://www.math.hmc.edu/~njp/ Nick Pippinger], not me.)
[[CATEGORY: Computer Science Eponyms]]
[[CATEGORY: Computer Science Eponyms]]

Latest revision as of 13:41, 12 May 2013

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