On the number of negations needed to compute parity functions
Tetsuro Nishino, Jaikumar Radhakrishnan · IEICE Transactions on Information and Systems · 1995
We exactly determine the number of negations needed to compute the parity functions and the complement of the parity functions. We show that with k NOT gates, parity can be computed on at most 2k+1-1 variables, and parity complement on at most 2k+1-2 variables. The two bounds are shown to be tight.