Klasse aller Folgen Boolescher Funktionen f_n : {0, 1}ⁿ → {0, 1}, die sich in Schaltkreisen mit durch 2 beschränktem Fan-in über dem Bausteinsatz AND, OR und NOT (Konjunktion, Disjunktion, NOT-Funktion) mit polynomiell vielen Bausteinen in Tiefe O(log^k n) berechnen lassen.

Funktionen in NC^k lassen sich mit vertretbarem Aufwand hardwaremäßig realisieren und sind bei Parallelverarbeitung sehr effizient auszuwerten. Die arithmetischen Operationen Addition, Subtraktion, Multiplikation und Division sind in NC¹ enthalten, Probleme der Linearen Algebra wie die Determinantenberechnung (über dem Körper {0, 1}) sind in NC² enthalten. Die Sprachklasse NC^k ist eine Teilmenge von AC^k und umfaßt AC^k−1.