NC

Builds on Boolean circuit L Formal language

Definition

Let $i \ge 1$ . Consider Boolean circuits with AND and OR gates of fan-in $2$ and NOT gates. A language $L \subseteq \set{0,1}^*$ is in $\mathrm{NC}^i$ if there are a polynomial $p$ , a constant $c$ and such circuits $C_n$ such that, for all $n \ge 2$ :

$C_n$ has $n$ inputs and at most $p(n)$ gates;
every path from an input to the output of $C_n$ passes through at most $c (\log n)^i$ gates;
for every $x \in \set{0,1}^n$ , $C_n(x) = 1$ if and only if $x \in L$ ;
a deterministic Turing machine computes a description of $C_n$ from $1^n$ using space $O(\log n)$ .

The class NC is $\bigcup_{i \ge 1} \mathrm{NC}^i$ .

Remarks

Example: the parity language $\set{x : x \text{ has an odd number of ones}}$ is in $\mathrm{NC}^1$ . The exclusive or $u \oplus v = (u \wedge \neg v) \vee (\neg u \wedge v)$ uses a constant number of gates and has constant depth. A balanced binary tree of such blocks over the $n$ inputs has $O(n)$ gates and depth $O(\log n)$ , and it is easy to describe in logarithmic space.

Non-example: let $C_n$ be a chain of $n$ exclusive-or blocks. This family also computes parity, but its depth grows linearly in $n$ , so it fails clause 2 for every $i$ .

Clause 4 is logspace uniformity; other uniformity conditions give the same class $\mathrm{NC}$ . The known inclusions are $\mathrm{NC}^1 \subseteq$ L $\subseteq$ NL $\subseteq \mathrm{NC}^2$ and $\mathrm{NC} \subseteq \mathrm{P}$ .

Reading path

To understand this page from the ground up, read these 4 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Boolean circuit concept
Formal language concept
L concept
NC definition

Tag	`BZ3N4E8RTX`
URI	`m2://BZ3N4E8RTX`
Kind	definition
Writing	W0 stub
MSC	68Q15, 68Q06, 68Q10
Defines	NC
Uses	Boolean circuit, L, Formal language
Changed	3 November 2026

NC

Definition

Remarks

Reading path

Further reading

What this page needs for W1

What links here