Difference between revisions 108480292 and 108480294 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>''c'' and ''k'' such that it can be solved in time <math>O((\log n)^c)</math> using <math>O(n^k)</math>[[Big O notation|''O'']](log<sup>''c''</sup>&nbsp;''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)

Equivalently, '''NC''' can be defined as those decision problems decidable by  a [[Boolean circuit|uniform Boolean circuit]] (which can be calculated from the length of the input) with [[polylogarithmic]] depth and a polynomial number of gates.

== The NC Hierarchy ==
'''NC'''<sup>''i''</sup> is the class of decision problems decidable by uniform boolean circuits with a polynomial number of gates and depth 
<math>O((\log n)^i)</math>''O''(log<sup>''i''</sup>&nbsp;''n''), or the class of decision problems solvable in time <math>O((\log n)^i)</math>''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.

(contracted; show full){{DEFAULTSORT:Nc (Complexity)}}
[[Category:Complexity classes]]
[[Category:Circuit complexity]]

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