Difference between revisions 108480367 and 108480374 on dewikiIn [[computational complexity theory|complexity theory]], the class '''NC''' (for "Nick's Class") is the set of [[decision problem]]s 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 exist constants ''c'' and ''k'' such that it can be solved in time [[Big O notation|''O'']](log<subp>''c''</subp> ''n'') using [[Big O notation|''O'']](''n''<sup>''k''</sup>) parallel processors. [[Stephen Cook]] coined the name "Nick's class" after [[Nick Pippenger]], who had done extensive research on circuits with polylogarithmic depth and polynomial size.
(contracted; show full)[[Category:Complexity classes]]
[[Category:Circuit complexity]]
[[de:NC (Komplexitätsklasse)]]
[[es:NC (clase de complejidad)]]
[[ko:NC (복잡도)]]
[[it:NC (complessità)]]
[[ja:NC (計算複雑性理論)]]
This site is not affiliated with or endorsed in any way by the Wikimedia Foundation or any of its affiliates. In fact, we fucking despise them.
|
