A language L is NC many-one reducible or NC reducible to L', written L ≤_m^NC L' if there is a function f in FNC such that x ∈ L if and only if f(x) ∈ L'.