文献

J-GLOBAL ID：201202296877921461   整理番号：12A1052367

超二次論理式サイズへ向けた候補となる論理関数

Candidate Boolean Functions towards Super-Quadratic Formula Size

著者 (1件)： UENO Kenya (Kyoto Univ., Kyoto, JPN)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 112  号： 93(COMP2012 12-25)  ページ： 49-55  発行年： 2012年06月14日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 短報  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： 本論文では,超二次論理式サイズ下界を証明するための可能性と限界について,以下の観点から探究する。まず,再帰的に定義される論理関数を考え,それらに対する一般的な論理式サイズ上界を与える。また,超二次論理式サイズが証明できる可能性のある候補論理関数として,厳密2ビット論理関数を基底として定義される再帰的論理関数を議論する。実際に,その論理式の複雑さが少なくともΩ(n²)であることを示す。さらに,Karchmer-Wigderson通信ゲームに対する最適なプロトコル分割数の構造から,多数決関数の論理式複雑さを解明することの難しさについて,偶奇判定論理関数と対比しながら考察する。(著者抄録)

シソーラス用語： *論理関数 ,  式 ,  *計算量
準シソーラス用語： 論理式 ,  *計算の複雑さ

分類 (1件)： 論理代数  (JB03000H)

タイトルに関連する用語 (3件)： 論理式 ,  サイズ ,  論理関数