Editing NC (complexity) (section)

=== Open problem: Is NC proper? ===
{{unsolved|computer science|Is the <math>\mathsf{NC}</math> hierarchy 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 ''j''&nbsp;≥&nbsp;''i'', 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>\mathsf{NC}^1 \subseteq \mathsf{NC}^2 \subseteq \cdots</math>
implies that the entire '''NC''' hierarchy "collapses" down to some level ''i''. Thus, there are 2 possibilities:

# <math>\mathsf{NC}^1 \subset \cdots \subset \mathsf{NC}^i \subset \cdots \subset \mathsf{NC}^{i+j} \subset \cdots \mathsf{NC}</math>
# <math>\mathsf{NC}^1 \subset \cdots \subset \mathsf{NC}^i = \cdots = \mathsf{NC}^{i+j} = \cdots \mathsf{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.

If there exists a problem that is '''NC'''-complete under '''LOGSPACE''' or '''NC'''<sup>''1''</sup> reductions, then the '''NC''' hierarchy collapses.<ref name=":0" />{{Pg|page=136}}