否定数限定反転回路の複雑さについて
書誌事項
- タイトル別名
-
- 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変数を反転する否定数限定回路にある種の制約を加え,その回路サイズが超線形下界をもつような二つの特殊な場合を紹介する.
収録刊行物
-
- 電子情報通信学会技術研究報告. COMP, コンピュテーション
-
電子情報通信学会技術研究報告. COMP, コンピュテーション 94 (26), 51-60, 1994-04-27
一般社団法人電子情報通信学会
- Tweet
詳細情報 詳細情報について
-
- CRID
- 1570291227422828288
-
- NII論文ID
- 110003191722
-
- NII書誌ID
- AN10013152
-
- 本文言語コード
- ja
-
- データソース種別
-
- CiNii Articles