On the Number of Negations Needed to Compute Parity Functions

Tetsuro NISHINO  Jaikumar RADHAKRISHNAN  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E78-D   No.1   pp.90-91
Publication Date: 1995/01/25
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: LETTER
Category: Algorithm and Computational Complexity
Keyword: 
computational complexity,  boolean circuit,  parity function,  

Full Text: PDF(152.1KB)
>>Buy this Article


Summary: 
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+11 variables, and parity complement on at most 2k+12 variables. The two bounds are shown to be tight.