Difference between revisions 108480279 and 108480285 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 <math>c</math> and <math>k</math> such that it can be solved in time <math>O((\log n)^(contracted; show full)

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.

=== Open problem: Is 
'''NC'''NC proper? ===
One major open question in [[computational complexity theory|complexity theory]] is whether or not every containment in the '''NC''' hierarchy is proper. It was observed by Papadimitriou that, if '''NC'''<sup>''i''</sup> = '''NC'''<sup>''i''+1</sup> for some ''i'', then '''NC'''<sup>'(contracted; show full)
[[Category:Complexity classes]]
[[Category:Circuit complexity]]

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