連数限定入力に対する否定数限定ソーティング回路

スポンサーリンク

概要

論文の詳細を見る
深さをclogn, NOTゲートの個数をclognに制限したとき, x_1, ..., x_nからx_1, ..., x_n を出力するインバータをO(n)個のゲートで構成可能か否かという問題が文献[TN94]で未解決問題として提起された.本論文では, (0^*1^*)^k0^*に属する系列をkブロック限定ということとし, 入力 x_1, ..., x_n を kブロック限定に限定した場合は, NOTゲートをO(k log n)個しか許さないとしても, インバーターはO(kn)個のゲートで計算できることを示した.さらに, この命題はインバーターの代りに x_1, ..., x_n を入力し, これを並べかえ y_1≥・・・≥y_n となる y_1, ..., y_n を出力するソーティング関数としても成立することにも言及する.
社団法人電子情報通信学会の論文
1998-03-24

著者

関連論文

もっと見る

スポンサーリンク