Editing NC (complexity) (section)

=== 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>.