Difference between revisions 108480339 and 108480342 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 ''c'' and ''k'' such that it can be solved in time [[Big O notation|(contracted; show full)
:<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 ... \subset \textbf(NC)^
{i+j} \subset \cdots \textbf{NC}</math>
# <math>\textbf{NC}^1 \subset \cdots \subset \textbf{NC}^i = ... = \textbf(NC)^{i+j} = \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 | 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 | isbn = 1-84628-297-7}} Lecture 12: Relation of ''NC'' to Time-Space Classes

{{ComplexityClasses}}

{{DEFAULTSORT:Nc (Complexity)}}
[[Category:Complexity classes]]
[[Category:Circuit complexity]]

[[de:NC (Komplexitätsklasse)]]
[[es:NC (clase de complejidad)]]
[[ko:NC (복잡도)]]
[[it:NC (complessità)]]
[[ja:NC (計算複雑性理論)]]