Difference between revisions 108480343 and 108480346 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)h a polynomial number of gates 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 
\subseteq \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:

(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 (計算複雑性理論)]]