Begriff aus der Theorie Boolescher Funktionen.

Eine Folge f = (f_n) Boolescher Funktionen ist auf eine Folge g = (g_n) Boolescher Funktionen NC¹-reduzierbar, Notation f ≤₁g, wenn f = (f_n) durch Schaltkreise S_n berechnet werden kann, die neben Bausteinen vom fan-in 2 auch Bausteine für gi, die zur Größe i und zur Tiefe ⌈ld(i)⌉ beitragen, enthalten dürfen. Dabei müssen die Schaltkreise S_n polynomielle Größe und logarithmische Tiefe haben.

NC¹-Reduktionen sind das angemessene Reduktionskonzept für die Sprachklasse non-uniform-NC^k.