最簡な論理式だけを生成するアルゴリズム

• Item type: SIG Technical Reports(1)
• 公開日: 2006-05-18
• タイトル: 最簡な論理式だけを生成するアルゴリズム
• タイトル / 言語: en
• タイトル: A procedure that generates a class of optimal Boolean formulas
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 群馬大学工学部情報工学科
• 著者所属(英): en
• 著者所属(英): Dept. of Computer Science, Gunma University
• 著者名: 天野, 一幸
• 著者名(英): Kazuyuki, Amano
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: ｎ変数論理関数fとｍ変数論理関数ｇに対して、f×gは(f×g)(x1 ... xnm)＝f(g(x1) ... g(xn))、ただし、xi＝(x(i-1)m+1 ... xim)で定義されるｎｍ変数論理関数を表すものとする。本稿では、以下の条件を満たす論理関数のクラスＧを与える: 任意のf＝f1×…fk(f1 ... fk∈Ｇ)に対して、"素直"な構成法によって与えられる論理式が常にfに対する最簡な論理式である。クラスＧは、例えば、全ての２変数関数、３変数関数256個のうち134個などを含む。この結果は、ｎ＝２ｋ変数パリティ関数の最簡な論理式のサイズが丁度ｎ2であることを示したKhzapchenkoによる結果の拡張と見ることができる(全てのiに対してfi＝x1＋x2と考える)。また、このような最簡な論理式のみを生成する手続きをも与える。本結果は本質的には、近年、量子敵対者法[1 2 8 10]において提案された、ある複雑さの尺度を綿密に解析したものである。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In this paper, we investigate the size of Boolean formulas for composite functions. For two Boolean functions ｆ:{0,1}n→{0,1} and g:{0,1}m→{0,1}, f×g denotes a Boolean function on ｎｍ variables defined by (f×g)(x1,...,xnm)＝ｆ(g(x1),...,g(xn)) where xi＝(x(i-1)m+1,...,xim). We give a class of base functions G such that for every function of the form f＝f1×…×fk with f1,...,fk∈G, a "naive" construction yields an optimal formula for f. The class G contains every two-variable functions, 134 out of 256 three-variable functions, and more. This can be viewed as a generalization of Khrapchenko's result that says that the formula size of the parity function on ｎ＝2k variables is ｎ2, which corresponds to the case fi＝x1＋x2 for every i. We also give a procedure that recursively generates Boolean formulas whose optimality is guaranteed. Our results are based on a careful inspection of a recently proposed complexity measure SumPI[7], which originated from the quantum adversary method [1,2,8,10].
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2006, 号 49(2006-AL-106), p. 1-8, 発行日 2006-05-18
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会