Negation-Limited Inverters of Linear Size

作者：Morizumi Hiroki^*; Suzuki Genki

来源：IEICE Transactions on Information and Systems, 2010, E93D(2): 257-262.

DOI：10.1587/transinf.E93.D.257

• circuit complexity
• negation-limited circuit
• inverter
• NOT gate

An inverter is a circuit which outputs (sic)x(1), (sic)x(2)., (sic)x, for any Boolean inputs x(1), x(2), ..., x(n). 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(n log n) and depth O(log n) and uses inverted right perpendicularlog(n + 1)inverted left perpendicular 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.

• 出版日期2010-2