講演名	1995/7/27 回路計算量における和算と乗算のある違いについて 築地 立家,
PDFダウンロードページ	PDFダウンロードページへ
抄録(和)	v_0からv_kに至る路v_0,...,v_kのv_iをその路の第i頂点と呼ぶ.有効グラフの二頂点v,v'について,vからv'に至る全ての路の第i頂点の個数をω(v,v',i;C)で表し,max_ω(v,v',i;C)をCの路幅と呼ぶ.本稿では,路幅が定数で押えられるような組合せ回路を考察する.和算はサイズO(n),深さO(log n),路幅O(1)の回路で実現されることがしられている.本稿では,これに対し,乗算を路幅O(1)の回路で計算するときのサイズの下界として,Ω(n logloglog n)を示す.
抄録(英)	A node v_i on a directed path v_0, v_1,...,v_k (from v_0 to v_k of length k) is called the i th node on the path. For two nodes v, v' in a directed acyclic graph C, let us denote by w(v,v',i;C) the number of i th node on a path from v to v', and call max_ ω(v,v',i;C) the path-width of C. We show that any Boolean shifter with a constant path-width must have Ω(n log log log n) of gates. As a corollary, the Boolean multiplication must have Ω(n log log log n) of gates to be computed on constant path-width circuits : the Boolean addition, on the other hand, have some construcitons of efficient circuits, O(n) of size, O(log n) of depth, and O(1) of path-width.
キーワード(和)	回路計算量 / 路幅 / シフト / 下界
キーワード(英)	circuit complexity / path-width / shifting / lower bound
資料番号
発行日

研究会情報
研究会	COMP
開催期間	1995/7/27(から1日開催)
開催地（和）
開催地（英）
テーマ（和）
テーマ（英）
委員長氏名（和）
委員長氏名（英）
副委員長氏名（和）
副委員長氏名（英）
幹事氏名（和）
幹事氏名（英）
幹事補佐氏名（和）
幹事補佐氏名（英）

講演論文情報詳細
申込み研究会	Theoretical Foundations of Computing (COMP)
本文の言語	ENG
タイトル（和）	回路計算量における和算と乗算のある違いについて
サブタイトル（和）
タイトル（英）	Some Difference between Addition and Multiplication on Circuit Complexity
サブタイトル（和）
キーワード(1)（和/英）	回路計算量 / circuit complexity
キーワード(2)（和/英）	路幅 / path-width
キーワード(3)（和/英）	シフト / shifting
キーワード(4)（和/英）	下界 / lower bound
第 1 著者 氏名（和/英）	築地 立家 / Tatsuie Tsukiji
第 1 著者 所属（和/英）	東京工業大学情報理工学研究科 Graduate School of Informatin Science and Engineering Tokyo Institute of Technology
発表年月日	1995/7/27
資料番号
巻番号（vol）	vol.95
号番号（no）	188
ページ範囲	pp.-
ページ数	5
発行日