| 講演名 | 1996/10/31 論理関数の複雑さと近似演算 天野 一幸, 丸岡 章, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | Razborov(1985)がクリーク関数を計算する単調論理回路のサイズに対する多項式を超える下界を証明して以来, Andreev(1985), AlonとBoppana(1987), Haken(1995), 天野と丸岡(1996)らが様々な手法を用いて, 特定の関数を計算する単調論理回路のサイズに対する指数関数の下界を証明した. 本稿では, 一見異なるこれらの証明が全て近似法と呼ばれる手法によるものか, または, その本質的な部分を損なわずに近似法による証明に再構成できることを示し, 更に, これらの証明の本質的な部分が全て類似の組合せ論的議論に基づいていることを明らかにする. また, この様な従来型論法の限界点についても議論し, サイズs(sは定数とする)のクリークが含まれるか否かを判定する関数を計算する単調論理回路のサイズの下界について, この型の証明では, 既知の最良の値を凌ぐ結果は導き得ないことを示す. |
| 抄録(英) | Since Razborov(1985) obtained superpolynomial lower bounds for monotone circuits that detect cliques in graphs, several results has been reported to obtain an exponential lower bound for monotone circuits that compute a certain function in the various ways, e.g. Andreev(1985). Alon and Boppana(1987), Haken(1995) and Amano and Maruoka(1996). In this paper, we show that all proofs for these results employ the approximation method or can be regarded as the proofs based on this method. Moreover, the counting arguments used in those proofs are quite similar. We also show that this type of proofs is too weak to improve lower bounds for monotone circuits that detect cliques of size s, for fixed s. |
| キーワード(和) | 単調複雑さ / 近似法 / 隘路数え上げ / クリーク関数 |
| キーワード(英) | monotone circuit complexity / approximation method / bottleneck counting / clique function |
| 資料番号 | COMP96-37 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 1996/10/31(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 論理関数の複雑さと近似演算 |
| サブタイトル（和） | |
| タイトル（英） | Cirsuit Complexity and Approximate Operations |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 単調複雑さ / monotone circuit complexity |
| キーワード(2)（和/英） | 近似法 / approximation method |
| キーワード(3)（和/英） | 隘路数え上げ / bottleneck counting |
| キーワード(4)（和/英） | クリーク関数 / clique function |
| 第 1 著者 氏名（和/英） | 天野 一幸 / Kazuyuki AMANO |
| 第 1 著者 所属（和/英） | 東北大学大学院情報科学研究科 Graduate School of Information Sciences, Tohoku University |
| 第 2 著者 氏名（和/英） | 丸岡 章 / Akira Maruoka |
| 第 2 著者 所属（和/英） | 東北大学大学院情報科学研究科 Graduate School of Information Sciences, Tohoku University |
| 発表年月日 | 1996/10/31 |
| 資料番号 | COMP96-37 |
| 巻番号（vol） | vol.96 |
| 号番号（no） | 343 |
| ページ範囲 | pp.- |
| ページ数 | 10 |
| 発行日 | |