A language L is P-hard under NC many-one reducibility if L' ≤_m^NC for every L' ∈ P. A language L is P-complete under NC reducibility if L ∈ P and L is P-hard.