Difference between revisions 108480252 and 108480254 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)

Equivalently, '''NC''' can be defined as those decision problems decidable by [[Boolean circuit|uniform Boolean circuits]]
 (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>, or the class of decision problems solvable in time <math>O((\log n)^i)</math> on a parallel computer with a polynomial number of processors. Clearly, we have

(contracted; show full){{ComplexityClasses}}

[[Category:Complexity classes]] [[Category:Circuit complexity]]

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