もっとも敏感な<i>k</i>-CNF
書誌事項
- タイトル別名
-
- Tight Bounds on the Average Sensitivity of <i>k</i>-CNF
この論文をさがす
抄録
論理関数 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) を参照されたい.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).
収録刊行物
-
- 研究報告アルゴリズム(AL)
-
研究報告アルゴリズム(AL) 2011 (7), 1-1, 2011-05-09
- Tweet
詳細情報 詳細情報について
-
- CRID
- 1570854177033111296
-
- NII論文ID
- 110008583105
-
- NII書誌ID
- AN1009593X
-
- 本文言語コード
- ja
-
- データソース種別
-
- CiNii Articles
- KAKEN