Check out my first novel, midnight's simulacra!
Nick's Class: Difference between revisions
From dankwiki
No edit summary |
No edit summary |
||
| 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.) | (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.)
