Difference between revisions 108480306 and 108480309 on dewiki

In [[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|(contracted; show full)

We can relate the '''NC''' classes to the space classes '''[[L (complexity)|L]]''' and '''[[NL (complexity)|NL]]'''.  From Papadimitriou 1994, Theorem 16.1:

:<math> \mathbf{NC}^1 \subseteq \mathbf{L} \subseteq \mathbf{NL} \subseteq \mathbf{NC}^2 \subseteq \mathbf{P}.</math><ref>[http://www.cs.mu.oz.au/677/notes/node18.html Nick's Class<!-- Bot generated title -->]
 {{dead link}}</ref>

Similarly, we have that '''NC'''<sup>''i''</sup> is equivalent to the problems solvable on an [[alternating Turing machine]] with <math>O(\log n)</math> space and <math>(\log n)^{O(1)}</math> alternations.{{fact}}

=== Open problem: Is NC proper? ===
(contracted; show full){{DEFAULTSORT:Nc (Complexity)}}
[[Category:Complexity classes]]
[[Category:Circuit complexity]]

[[de:NC (Komplexitätsklasse)]]
[[es:Clase de Nick]]
[[ko:NC (복잡도)]]
[[ja:NC (計算複雑性理論)]]