NC (complexity) - The NC Hierarchy

The NC Hierarchy

NCi is the class of decision problems decidable by uniform boolean circuits with a polynomial number of gates of at most two inputs and depth O(logi n), or the class of decision problems solvable in time O(logi n) on a parallel computer with a polynomial number of processors. Clearly, we have

which forms the NC-hierarchy.

We can relate the NC classes to the space classes L and NL and AC.

The NC classes are related to the AC classes, which are defined similarly, but with gates having unbounded fanin. For each i, we have

As an immediate consequence of this, we have that NC = AC. It is known that both inclusions are strict for i = 0.

Similarly, we have that NC is equivalent to the problems solvable on an alternating Turing machine restricted to at most two options at each step with space and alternations.