Difference between revisions 108480481 and 108480487 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)
* 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 na
tiïvely 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 ==
(contracted; show full)[[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)]]