もっとも敏感な<i>k</i>-CNF

• Item type: SIG Technical Reports(1)
• 公開日: 2011-05-09
• タイトル: もっとも敏感な<i>k</i>-CNF
• タイトル / 言語: en
• タイトル: Tight Bounds on the Average Sensitivity of <i>k</i>-CNF
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 群馬大学大学院工学研究科
• 著者所属(英): en
• 著者所属(英): Depertment of Computer Science, Gunma University
• 著者名: 天野, 一幸
• 著者名(英): Kazuyuki, Amano
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 論理関数 f:{0, 1}n → {0, 1} の感受度とは，一様分布に従って選ばれる入力 x に対する，f(x) ≠ f(xi) を満たす添え字iの個数の期待値である．ここで xi は x のiビット目を反転して得られる系列を表す．各節のリテラルの個数が k 個以下に制限された CNF 式を k-CNF 式と呼ぶ．本発表では，k-CNF 式で表現可能な任意の論理関数の感受度が k 以下であることを示す．k 変数パリティ関数の感受度は k であるから，この上界はタイトである．証明等の詳細については，文献 1) を参照されたい．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: The average sensitivity of a Boolean function is the expectation, given a uniformly random input, of the number of input bits which when flipped change the output of the function. A k-CNF formula is a formula in conjunctive normal form (CNF) containing only clauses of length at most k. In this talk, we show that every Boolean function represented by a k-CNF has average sensitivity at most k. This bound is tight since the parity function on k variables has average sensitivity k. This work has appeared in 1).
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2011-AL-135, 号 7, p. 1-1, 発行日 2011-05-09
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会