否定数限定反転回路の複雑さについて

  • 田中 圭介
    北陸先端科学技術大学院大学情報科学研究科
  • 西野 哲朗
    北陸先端科学技術大学院大学情報科学研究科

書誌事項

タイトル別名
  • On the Complexity of Negation-Limited Inverters

この論文をさがす

抄録

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

収録刊行物

キーワード

詳細情報 詳細情報について

  • CRID
    1570291227422828288
  • NII論文ID
    110003191722
  • NII書誌ID
    AN10013152
  • 本文言語コード
    ja
  • データソース種別
    • CiNii Articles

問題の指摘

ページトップへ