| 講演抄録／キーワード |
| 講演名 |
2006-06-23 11:10
Reductions for Monotone Boolean Circuits
Kazuo Iwama・○Hiroki Morizumi（Kyoto Univ.） |
| 抄録 |
（和） |
ソート関数やマージ関数を含む論理関数の大きなクラス（NLOGと呼ぶことにする）の単調回路サイズの上界は$O(n\log n)$である，つまり2入力のAND/OR素子$O(n\log n)$による回路が存在する．通常のAND/OR素子以外に$r (\geq 2)$入力$r' (\geq 1)$出力の単調論理関数$F$を実現するより強力な``$F$素子''が任意の数だけ使用できる場合を考える．AND/OR素子のコストは1であるが，$F$素子のコストは$r$であるとする．NLOGの論理関数$f$が全体のコストが$o(n\log n)$のAND/OR/$F$による回路で計算されるならば$f$は$F$-Easyであるという．本論文では，マージ関数が$r' \leq r/\log r$を満たす任意の単調関数$F$に対して$F$-Easyではないことを示す． |
| （英） |
The large class, say {\it NLOG}, of Boolean functions, including 0-1 Sort and 0-1 Merge, have an upper bound of $O(n\log n)$ for their monotone circuit size, i.e., have circuits with $O(n\log n)$ AND/OR gates of fan-in two. Suppose that we can use, besides such normal AND/OR gates, any number of more powerful ``$F$-gates'' which realize a monotone Boolean function $F$ with $r (\geq 2)$ inputs and $r' (\geq 1)$ outputs. Note that the cost of each AND/OR gate is one and we assume that the cost of each $F$-gate is $r$. Now we define: A Boolean function $f$ in NLOG is said to be $F$-Easy if $f$ can be computed by a circuit with AND/OR/$F$ gates whose total cost is $o(n\log n)$. In this paper we show that 0-1 Merge is not $F$-Easy for an arbitrary monotone function $F$ such that $r' \leq r/\log r$. |
| キーワード |
（和） |
回路計算量 / 単調回路 / 下界 / マージ関数 / 多数決関数 / / / |
| （英） |
circuit complexity / monotone circuit / lower bound / merging function / majority function / / / |
| 文献情報 |
信学技報, vol. 106, no. 128, COMP2006-19, pp. 15-19, 2006年6月. |
| 資料番号 |
COMP2006-19 |
| 発行日 |
2006-06-16 (COMP) |
| ISSN |
Print edition: ISSN 0913-5685 |
| PDFダウンロード |
|