Difference between revisions 108480254 and 108480259 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) parallel computer with a central pool of memory, and any processor can access any bit of memory in constant time.  The definition of '''NC''' is not affected by the choice of how the PRAM handles simultaneous access to a single bit by more than one processor. It can be CRCW, CREW, or EREW. See [[parallel random access machine|PRAM]] for descriptions of those models.  

Equivalently, '''NC''' can be defined as those decision problems decidable by 
 a [[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 p(contracted; show full){{ComplexityClasses}}

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

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