Difference between revisions 108480451 and 108480461 on dewiki

{{unsolved|computer science|Is '''NC''' {{=}} '''P''' ?}}
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 cons(contracted; show full)

Often algorithms for those problems had to be separately invented and could not be naively adapted from well-known algorithms - Gaussian elimination and Euclidean algorithm rely on operations performed in sequence. One might contrast [[ripple carry adder]] with a [[carry-lookahead adder]].

== The NC Hierarchy ==
'''NC'''<sup>''i''</sup> is the class of decision problems decidable by uniform boolean circuits with a polynomial number of gates 
of at most two inputs and depth ''O''(log<sup>''i''</sup>&nbsp;''n''), or the class of decision problems solvable in time ''O''(log<sup>''i''</sup>&nbsp;''n'') on a parallel computer with a polynomial number of processors. Clearly, we have

:<math>\textbf{NC}^1 \subseteq \textbf{NC}^2 \subseteq \cdots \subseteq \textbf{NC}^i \subseteq \cdots \textbf{NC}</math>

which forms the '''NC'''-hierarchy.

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>

Similarly, we have that '''NC''' is equivalent to the problems solvable on an [[alternating Turing machine]] restricted to at most two options at each step with <math>O(\log n)</math> space and <math>(\log n)^{O(1)}</math> alternations.<ref>{{cite journal|author=S. Bellantoni and I. Oitavem|title=Separating NC along the delta axis|journal=Theoretical Computer Science|volume=318|year=2004|pages=57–78}}</ref>

=== Open problem: Is NC proper? ===
(contracted; show full)[[Category:Circuit complexity]]

[[de:NC (Komplexitätsklasse)]]
[[es:NC (clase de complejidad)]]
[[ko:NC (복잡도)]]
[[it:NC (complessità)]]
[[ja:NC (計算複雑性理論)]]
[[vi:NC (độ phức tạp)]]