Difference between revisions 108480271 and 108480275 on dewiki

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 constants <math>c</math> and <math>k</math> such that it can be solved in time <math>O((\log n)^(contracted; show full)

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) with [[polylogarithmic]] depth and a polynomial number of gates.

== 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 <math>O((\log n)^i)</math>, or the class of decision problems solvable in time <math>O((\log n)^i)</math> on a parallel computer with a polynomial number of processors. Clearly, we have

<math>\textbf{NC}^1 \subseteq \textbf{NC}^2 \subseteq \cdots \subseteq \textbf{NC}^i \subseteq \cdots \subseteq \textbf{NC}</math>

which forms the '''NC'''-hierarchy.

We can relate the '''NC''' classes to the space classes '''[[L (complexity)|L]]''' and '''[[NL (complexity)|NL]]'''.  From Papadimitriou 1994, Theorem 16.1:

<math> \mathbf{NC^1 \subseteq L \subseteq NL \subseteq NC^2 \subseteq P} </math><ref>[http://www.cs.mu.oz.au/677/notes/node18.html Nick's Class<!-- Bot generated title -->]</ref>

Similarly, we have that '''NC'''<sup>''i''</sup> is equivalent to the problems solvable on an [[alternating Turing machine]] with <math>O(\log n)</math> space and <math>(\log n)^{O(1)}</math> alternations.

=== Open problem: Is '''NC''' proper? ===
⏎
⏎
One major open question in [[computational complexity theory|complexity theory]] is whether or not every containment in the '''NC''' hierarchy is proper. It was observed by Papadimitriou that, if '''NC'''<sup>''i''</sup> = '''NC'''<sup>''i''+1</sup> for some ''i'', then '''NC'''<sup>''i''</sup> = '''NC'''<sup>''j''</sup> for all <math>j \geq i</math>, and as a result, '''NC'''<sup>''i''</sup> = '''NC'''. This observation is known as '''NC'''-hierarchy collapse because even a single equality in the chain of containments <math>\textbf{NC}^1 \subseteq \textbf{NC}^2 \subseteq \cdots</math> implies that the entire '''NC''' hierarchy "collapses" down to some level ''i''. Thus, there are 2 possibilities:

# <math>\textbf{NC}^1 \subset \cdots \subset \textbf{NC}^i \subset \cdots \subset \textbf{NC}</math>
# <math>\textbf{NC}^1 \subset \cdots \subset \textbf{NC}^i = \cdots = \textbf{NC}</math>

It is widely believed that (1) is the case, although no proof as to the truth of either statement has yet been discovered.

==References==
⏎
⏎
<references/>
* Greenlaw, Raymond, James Hoover, and Walter Ruzzo. ''Limits To Parallel computation; P-Completeness Theory''. ISBN 0-19-508591-4
* 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 | id = ISBN 0-201-53082-1}} Section 15.3: The class '''NC''', pp.375&ndash;381.
* {{cite book|author = [[Dexter Kozen]] | year = 2006 | title = Theory of Computation | publisher = Springer | id = ISBN 1-84628-297-7}} Lecture 12: Relation of ''NC'' to Time-Space Classes

{{ComplexityClasses}}

[[Category:Complexity classes]]  ⏎
⏎
[[Category:Circuit complexity]]

[[de:NC (Komplexitätsklasse)]]
[[es:Clase de Nick]]
[[ko:NC (복잡도)]]
[[ja:NC (計算複雑性理論)]]