否定数限定反転回路の複雑さについて On the Complexity of Negation-Limited Inverters

この論文をさがす

著者

    • 田中 圭介 Tanaka Keisuke
    • 北陸先端科学技術大学院大学情報科学研究科 School of Information Science,Japan Advanced Institute of Science and Technology,Hokuriku
    • 西野 哲朗 Nishino Tetsuro
    • 北陸先端科学技術大学院大学情報科学研究科 School of Information Science,Japan Advanced Institute of Science and Technology,Hokuriku

抄録

否定数限定回路とは,回路中で使用できるNOTゲートの個数をlog(n+1)に制限した組合せ回路である.本稿では,n変数を反転する否定数限定回路(反転回路)の複雑さについて考察する.本研究以前に知られている反転回路のサイズの最良の上界は,O(n^2(logn)^2)である.本稿ではまず,この上界をO(n(logn)^2)に改良できることを示す.次に,反転回路のサイズと深さに関してそれぞれ,5n+3log(n+1)-6および4log(n+1)+2の下界を示す.さらに,n変数を反転する否定数限定回路にある種の制約を加え,その回路サイズが超線形下界をもつような二つの特殊な場合を紹介する.

A negation-limited circuit is a combinational circuit which includes at most log(n+1)NOT gates.We call a negation-limited circuit which inverts n variables an inverter.In this paper,we investigate the complexity of the inverters.For the size of the inverters,we give a new O(n(logn)^2)upper bound as well as a 5n+ 3log(n+1)-6 lower bound.For the depth of the inverters,we give a 4log(n+1)+2 lower bound.Furthermore,we show two superlinear lower bounds on the size of inverters.

収録刊行物

  • 電子情報通信学会技術研究報告. COMP, コンピュテーション

    電子情報通信学会技術研究報告. COMP, コンピュテーション 94(26), 51-60, 1994-04-27

    一般社団法人電子情報通信学会

各種コード

  • NII論文ID(NAID)
    110003191722
  • NII書誌ID(NCID)
    AN10013152
  • 本文言語コード
    JPN
  • データ提供元
    NII-ELS 
ページトップへ