Negation-Limited Inverters of Linear Size

Hiroki MORIZUMI  Genki SUZUKI  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E93-D   No.2   pp.257-262
Publication Date: 2010/02/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E93.D.257
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science)
Category: 
Keyword: 
circuit complexity,  negation-limited circuit,  inverter,  NOT gate,  

Full Text: PDF>>
Buy this Article



Summary: 
An inverter is a circuit which outputs ¬ x1, ¬ x2, ..., ¬ xn for any Boolean inputs x1, x2, ..., xn. We consider constructing an inverter with AND gates and OR gates and a few NOT gates. Beals, Nishino and Tanaka have given a construction of an inverter which has size O(nlog n) and depth O(log n) and uses ⌈ log (n+1) ⌉ NOT gates. In this paper we give a construction of an inverter which has size O(n) and depth log 1+o(1)n and uses log 1+o(1)n NOT gates. This is the first negation-limited inverter of linear size using only o(n) NOT gates. We also discuss implications of our construction for negation-limited circuit complexity.