もっとも敏感な<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) を参照されたい.
- 2011-05-09
著者
関連論文
- Clifford+π/8量子回路の計算能力
- 方形描画(フロアプラン)の個数について:厳密数え上げと下界と上界
- 部分グラフ同型性判定の回路計算量について
- 部分グラフ同型性判定の回路計算量について
- DS-1-3 多項式しきい値関数密度の上界の改善(DS-1.COMP学生シンポジウム,シンポジウムセッション)
- もっとも敏感なk-CNF
- グラフの正方格子上への単位長配置について (アルゴリズムと計算理論の新展開)
- ハッピーエンド問題に対する極値的頂点集合の構造(アルゴリズムとデータ構造・計算複雑度)
- ハッピーエンド問題に対する極値的頂点集合の構造