A Relationship between the Number of Negations and the Circuit Size

Keisuke TANAKA  Tetsuro NISHINO  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E79-D   No.9   pp.1355-1357
Publication Date: 1996/09/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8532
Type of Manuscript: LETTER
Category: Algorithm and Computational Complexity
Keyword: 
computational complexity,  theory of computation,  

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




Summary: 
We show a relationship between the number of negations in circuits and the size of circuits. More precisely, we construct a Boolean function Hn, and show that there exists an integer t, which can range over only two different values, such that the removal of one NEGATION gate causes an exponential growth of the optimal circuit size for Hn.