Difference between revisions 108480285 and 108480292 on dewiki

< previous diff
next diff >
Benutzer:Schreiber/NC (complexity)
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)
* {{cite book|author = [[Christos Papadimitriou]] | year = 1993 | title = Computational Complexity | publisher = Addison Wesley | edition = 1st edition | isbn = 0-201-53082-1}} Section 15.3: The class '''NC''', pp.375&ndash;381.
* {{cite book|author = [[Dexter Kozen]] | year = 2006 | title = Theory of Computation | publisher = Springer | isbn = 1-84628-297-7}} Lecture 12: Relation of ''NC'' to Time-Space Classes

{{ComplexityClasses}}


{{DEFAULTSORT:Nc (Complexity)}}⏎
[[Category:Complexity classes]]
[[Category:Circuit complexity]]

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