| 講演名 | 2014-10-08 多くの充足解を持つ和積形論理式のインプリカントの大きさについて ケイン ダニエル, 渡辺 治, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 任意の命題論理関数F(X_1,...,X_N)で,2^<-N>^δ・2^N個の充足可能解を持ち,さらに,高々N^d個の節から成るCNF論理式で表現できるものを考える(ただし,δ,0<δ<1とd<1は適当な定数).このとき,ある定数α>0が存在して,Fに対してある特定の高々αN個の変数の値を決めることで,その論理式を真にすることができることを示す.別の言い方をすれば,Fは,大きさ≦αNのインプリカントを持つことを示す. |
| 抄録(英) | Consider any Boolean function F(X_1, ... , X_N) that has more than 2^<-N>^δ・2^N satisfying assignments for some δ, 0 < δ < 1, and that can be expressed by a CNF formula with at most N^d clauses for some d > 0. Then how many variables do we need to fix in order to satisfy F? We show that one can always find some "short" partial assignment on which F evaluates to 1 by fixing at most αN variables for some constant α < 1; that is, F has an implicant of size ≦ αN. A lower bound for such a is also shown in terms of δ and d. |
| キーワード(和) | インプリカント(積項) / 和積形論理式 / 充足可能性問題 |
| キーワード(英) | implicant / CNF formula / satisfiability problem |
| 資料番号 | COMP2014-31 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2014/10/1(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | 多くの充足解を持つ和積形論理式のインプリカントの大きさについて |
| サブタイトル（和） | |
| タイトル（英） | Implicant Size of a CNF Formula with Many Satisfying Assignments |
| サブタイトル（和） | |
| キーワード(1)（和/英） | インプリカント(積項) / implicant |
| キーワード(2)（和/英） | 和積形論理式 / CNF formula |
| キーワード(3)（和/英） | 充足可能性問題 / satisfiability problem |
| 第 1 著者 氏名（和/英） | ケイン ダニエル / Daniel KANE |
| 第 1 著者 所属（和/英） | スタンフォード大学数学科 Dept. of Mathematics, Stanford Univ. |
| 第 2 著者 氏名（和/英） | 渡辺 治 / Osamu WATANABE |
| 第 2 著者 所属（和/英） | 東京工業大学数理・計算科学専攻 Dept. of Math. & Comput. Sci. |
| 発表年月日 | 2014-10-08 |
| 資料番号 | COMP2014-31 |
| 巻番号（vol） | vol.114 |
| 号番号（no） | 238 |
| ページ範囲 | pp.- |
| ページ数 | 7 |
| 発行日 | |