Difference between revisions 108480496 and 108587690 on dewiki

< previous diff
Benutzer:Schreiber/NC (complexity)
{{unsolved|computer science|Is '''NC''' {{=}} '''P''' ?}}
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 cons(contracted; show full)
* {{cite book|author = [[Dexter Kozen]] | year = 1992 | title = The design and analysis of algorithms}} Lectures 28 - 34 and 36
* {{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:NC (clase de complejidad)]]
[[ko:NC (복잡도)]]
[[it:NC (complessità)]]
[[ja:NC (計算複雑性理論)]]
[[vi:NC (độ phức tạp)]]