Editing NC (complexity) (section)

== 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
* Integer addition, multiplication and division;
* [[Matrix multiplication]], determinant, [[matrix inverse|inverse]], rank;
* Polynomial GCD, by a reduction to linear algebra using [[Sylvester matrix]]
* Finding a maximal matching.

Often algorithms for those problems had to be separately invented and could not be naï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]].

=== Example ===
An example of problem in NC<sup>1</sup> is the parity check on a bit string.<ref>{{cite web|url=https://lin-web.clarkson.edu/~alexis/PCMI/Notes/lectureB02.pdf|title=Lecture 2: The Complexity of Some Problems|date=2000-07-18|author1=David Mix Barrington|author2=Alexis Maciel|work=IAS/PCMI Summer Session 2000 - Clay Mathematics Undergraduate Program - Basic Course on Computational Complexity|publisher=[[Clarkson University]]|accessdate=2021-11-11}}</ref> The problem consists in counting the number of 1s in a string made of 1 and 0. A simple solution consists in summing all the string's bits. Since [[addition]] is associative, <math display="block">x_1 + \cdots + x_n = \left(x_1 + \cdots + x_{\frac{n}{2}}\right) + \left(x_{\frac{n}{2} + 1} + \cdots + x_n\right).</math> Recursively applying such property, it is possible to build a [[binary tree]] of length <math>O(\log(n))</math> in which every sum between two bits <math>x_i</math> and <math>x_j</math> is expressible by means of basic [[logical operator]]s, e.g. through the boolean expression <math>(x_i \land \neg x_j) \lor (\neg x_i \land x_j)</math>.