| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2012-06-21 13:45 超二次論理式サイズへ向けた候補となる論理関数 ○上野賢哉（京大）  COMP2012-18 |
|
| 抄録 | （和） | 本論文では，超二次論理式サイズ下界を証明するための可能性と限界について，以下の観点から探究する．まず，再帰的に定義される論理関数を考え，それらに対する一般的な論理式サイズ上界を与える．また，超二次論理式サイズが証明できる可能性のある候補論理関数として，厳密２ビット論理関数を基底として定義される再帰的論理関数を議論する．実際に，その論理式の複雑さが少なくとも$\Omega(n^2)$であることを示す．さらに，Karchmer-Wigderson通信ゲームに対する最適なプロトコル分割数の構造から，多数決関数の論理式複雑さを解明することの難しさについて，偶奇判定論理関数と対比しながら考察する． |
| （英） | In this paper, we explore possibilities and difficulties to prove super-quadratic formula size lower bounds from the following aspects. First, we consider recursive Boolean functions and prove their general formula size upper bounds. We also discuss candidate recursive Boolean functions which have possibilities to prove super-quadratic formula size lower bounds based on the exact 2-bit Boolean function. We show that its formula complexity is at least $\Omega(n^2)$. Next, we observe the reason of difficulty of resolving formula complexity of the majority function in contrast with the parity function in terms of structure of an optimal protocol partition for the Karchmer-Wigderson communication game. | |
| キーワード | （和） | 論理関数 / 計算量理論 / 論理式の複雑さ / / / / / |
| （英） | Boolean Function / Computational Complexity / Formula Complexity / / / / / | |
| 文献情報 | 信学技報, vol. 112, no. 93, COMP2012-18, pp. 49-55, 2012年6月. | |
| 資料番号 | COMP2012-18 | |
| 発行日 | 2012-06-14 (COMP) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2012-18 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2012-06-21 - 2012-06-21 |
| 開催地（和） | 北海道大学 |
| 開催地（英） | Hokkaido University |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2012-06-COMP |
| 本文の言語 | 英語（日本語タイトルあり） |
| タイトル（和） | 超二次論理式サイズへ向けた候補となる論理関数 |
| サブタイトル（和） | |
| タイトル（英） | Candidate Boolean Functions towards Super-Quadratic Formula Size |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 論理関数 / Boolean Function |
| キーワード(2)（和/英） | 計算量理論 / Computational Complexity |
| キーワード(3)（和/英） | 論理式の複雑さ / Formula Complexity |
| キーワード(4)（和/英） | / |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 上野 賢哉 / Kenya Ueno / |
| 第1著者 所属（和/英） | 京都大学 (略称： 京大) Kyoto University (略称： Kyoto Univ.) |
| 第2著者 氏名（和/英/ヨミ） | / / |
| 第2著者 所属（和/英） | (略称： ) (略称： ) |
| 第3著者 氏名（和/英/ヨミ） | / / |
| 第3著者 所属（和/英） | (略称： ) (略称： ) |
| 第4著者 氏名（和/英/ヨミ） | / / |
| 第4著者 所属（和/英） | (略称： ) (略称： ) |
| 第5著者 氏名（和/英/ヨミ） | / / |
| 第5著者 所属（和/英） | (略称： ) (略称： ) |
| 第6著者 氏名（和/英/ヨミ） | / / |
| 第6著者 所属（和/英） | (略称： ) (略称： ) |
| 第7著者 氏名（和/英/ヨミ） | / / |
| 第7著者 所属（和/英） | (略称： ) (略称： ) |
| 第8著者 氏名（和/英/ヨミ） | / / |
| 第8著者 所属（和/英） | (略称： ) (略称： ) |
| 第9著者 氏名（和/英/ヨミ） | / / |
| 第9著者 所属（和/英） | (略称： ) (略称： ) |
| 第10著者 氏名（和/英/ヨミ） | / / |
| 第10著者 所属（和/英） | (略称： ) (略称： ) |
| 第11著者 氏名（和/英/ヨミ） | / / |
| 第11著者 所属（和/英） | (略称： ) (略称： ) |
| 第12著者 氏名（和/英/ヨミ） | / / |
| 第12著者 所属（和/英） | (略称： ) (略称： ) |
| 第13著者 氏名（和/英/ヨミ） | / / |
| 第13著者 所属（和/英） | (略称： ) (略称： ) |
| 第14著者 氏名（和/英/ヨミ） | / / |
| 第14著者 所属（和/英） | (略称： ) (略称： ) |
| 第15著者 氏名（和/英/ヨミ） | / / |
| 第15著者 所属（和/英） | (略称： ) (略称： ) |
| 第16著者 氏名（和/英/ヨミ） | / / |
| 第16著者 所属（和/英） | (略称： ) (略称： ) |
| 第17著者 氏名（和/英/ヨミ） | / / |
| 第17著者 所属（和/英） | (略称： ) (略称： ) |
| 第18著者 氏名（和/英/ヨミ） | / / |
| 第18著者 所属（和/英） | (略称： ) (略称： ) |
| 講演者 | 第1著者 |
| 発表日時 | 2012-06-21 13:45:00 |
| 発表時間 | 25分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2012-18 |
| 巻番号（vol） | vol.112 |
| 号番号（no） | no.93 |
| ページ範囲 | pp.49-55 |
| ページ数 | 7 |
| 発行日 | 2012-06-14 (COMP) |
[研究会発表申込システムのトップページに戻る]