Negation-Limited Inverters of Linear Size

スポンサーリンク

概要

• 論文の詳細を見る

• 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 log1+o(1)n and uses log1+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-02-01

著者

• Suzuki Genki

  School Of Engineering Tohoku University

• MORIZUMI Hiroki

  Graduate School of Information Sciences, Tohoku University

• Morizumi Hiroki

  Graduate School Of Information Sciences Tohoku University

関連論文

• Negation-Limited Inverters of Linear Size

スポンサーリンク