Difference between revisions 108480134 and 108480135 on dewiki

< previous diff
next diff >
Benutzer:Schreiber/NC (complexity)
In [[computational complexity theory|complexity theory]], the class '''NC''' ("Nick's Class") is the set of [[decision problem|decision problems]] decidable in polylogarithmic time on a [[parallel computing|parallel computer]] with a polynomial number of processors.  In other words, a problem is in '''NC''' if there are constants ''c'' and ''k'' such that it can be solved in time O((log '&(contracted; show full)

[[Stephen Cook]] coined the name NC ("Nick's class") after [[Nick Pippenger]], who had done extensive research on circuits with polylogarithmic depth and polynomial size.

==Reference==
* Greenlaw, Raymond, James Hoover, and Walter Ruzzo. ''Limits To Parallel computation; P-Completeness Theory''. ISBN 0195085914
⏎
* Heribert Vollmer. ''[http://www.thi.uni-hannover.de/forschung/publikationen/cc/index.en.php Introduction to Circuit Complexity -- A Uniform Approach]''. ISBN 3-540-64310-9

{{ComplexityClasses}}[[Category:Complexity classes]]