Difference between revisions 108480401 and 108480409 on dewiki

{{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)

[[RNC (complexity)|RNC]] is a class extending NC with access to randomness.

== Problems in NC ==
As with '''P''', by a slight abuse of language, one might classify function problems and search problems as being in '''NC'''. '''NC''' is known to include many problems, including
* 
Computation of matrix determinant, inverse, rank;
* Finding a maximal matching;
* Polynomial GCD (it is open whether integer GCD is in NC)Integer addition, multiplication and division;
* Matrix multiplication, determinant, inverse, rank;
* Polynomial GCD, by a reduction to linear algebra using [[Sylvester matrix]] (it is open whether integer GCD is in NC);
* Finding a maximal matching.

Often algorithms for those problems had to be separately invented and could not be naively adapted from well-known algorithms - Gaussian elimination and Euclidean algorithm rely on operations performed in sequence. One might contrast [[ripple carry adder]] with a [[carry-lookahead adder]].

== 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 ''O''(log<sup>''i''</sup>&nbsp;''n''), or the class of decision problems solvable in time ''O''(log<sup>''i''</sup>&nbsp;''n'') on (contracted; show full)
* Heribert Vollmer. ''Introduction to Circuit Complexity -- A Uniform Approach''. ISBN 3-540-64310-9
* {{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 = 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)]]