Editing NC (complexity) (section)

{{Short description|Class in computational complexity theory}}
{{unsolved|computer science|{{tmath|1= \mathsf{NC} \overset{?}{=} \mathsf{P} }}}}
In [[computational 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 with input size ''n'' is in '''NC''' if there exist constants ''c'' and ''k'' such that it can be solved in time {{math|''[[Big O notation|O]]''((log ''n'')<sup>''c''</sup>)}} using {{math|''O''(''n''<sup>''k''</sup>)}} parallel processors. [[Stephen Cook]]<ref>{{Cite journal|last=Cook|first=S.A.|title=Towards a complexity theory of synchronous parallel computation|journal=L'Enseignement Mathématique|date=1981|volume=27|pages=99–124|url=http://citeseerx.ist.psu.edu/showciting?cid=1672592|language=en|archive-url=https://web.archive.org/web/20220310162138/http://citeseerx.ist.psu.edu/showciting?cid=1672592|archive-date=2022-03-10}}</ref><ref>{{Cite journal|last=Cook|first=Stephen A.|date=1985-01-01|title=A taxonomy of problems with fast parallel algorithms|journal=Information and Control|series=International Conference on Foundations of Computation Theory|language=en|volume=64|issue=1|pages=2–22|doi=10.1016/S0019-9958(85)80041-3|issn=0019-9958|doi-access=free}}</ref> coined the name "Nick's class" after [[Nick Pippenger]], who had done extensive research<ref>{{Cite journal|last=Pippenger|first=Nicholas|date=1979|title=On simultaneous resource bounds|url=https://www.infona.pl//resource/bwmeta1.element.ieee-art-000004568025|journal=20th Annual Symposium on Foundations of Computer Science (SFCS 1979)|language=en|pages=307–311|doi=10.1109/SFCS.1979.29|s2cid=7029313 |issn=0272-5428}}</ref> on circuits with polylogarithmic depth and polynomial size.<ref name=AB120>Arora & Barak (2009) p.120</ref> As in the case of [[circuit complexity]] theory, usually the class has an extra constraint that the circuit family must be ''uniform'' ([[NC (complexity)#Uniformity|see below]]).

Just as the class '''[[P (complexity)|P]]''' can be thought of as the tractable problems ([[Cobham's thesis]]), so '''NC''' can be thought of as the problems that can be efficiently solved on a parallel computer.<ref name=AB118>Arora & Barak (2009) p.118</ref> '''NC''' is a subset of '''P''' because polylogarithmic parallel computations can be simulated by polynomial-time sequential ones. It is unknown whether '''NC''' = '''P''', but most researchers suspect this to be false, meaning that there are probably some tractable problems that are "inherently sequential" and cannot significantly be sped up by using parallelism. Just as the class '''[[NP-complete]]''' can be thought of as "probably intractable", so the class '''[[P-complete]]''', when using '''NC''' reductions, can be thought of as "probably not parallelizable" or "probably inherently sequential".

The parallel computer in the definition can be assumed to be a ''parallel, random-access machine'' ([[parallel random access machine|PRAM]]).  That is a parallel computer with a central pool of memory, and any processor can access any bit of memory in constant time.  The definition of '''NC''' is not affected by the choice of how the PRAM handles simultaneous access to a single bit by more than one processor. It can be CRCW, CREW, or EREW. See [[parallel random access machine|PRAM]] for descriptions of those models.

Equivalently, '''NC''' can be defined as those decision problems decidable by a [[Boolean circuit|uniform Boolean circuit]] (which can be calculated from the length of the input, for NC, we suppose we can compute the Boolean circuit of size ''n'' in logarithmic space in ''n'') with [[polylogarithmic]] depth and a polynomial number of gates with a maximum fan-in of 2.

'''RNC''' is a class extending '''NC''' with access to randomness.