NC

Summary

NC, Nick's class, is the complexity class of problems decided by uniform families of Boolean circuits of polynomial size and polylogarithmic depth. Its circuits use gates with at most two inputs. It is the standard formal notion of a problem that can be solved very fast in parallel with a reasonable number of processors. It is split into levels $\mathrm{NC}^i$, of depth $O(\log^i n)$. It is contained in P, and it is a major open question whether $\mathrm{NC} = \mathrm{P}$.