DS-1-3 多項式しきい値関数密度の上界の改善(DS-1.COMP学生シンポジウム,シンポジウムセッション)
スポンサーリンク
概要
- 論文の詳細を見る
n変数ブール関数f:{1,-1}^n→{1,-1}とn変数多項式p:R^n→Rにっいて,任意の入力xでsgn(p(x))=f(x)が成立しているとき,fはpにより符号表現されている,あるいはpはfのPTF表現であるという.ブール関数fの多項式しきい値関数密度(PTF密度)とは,fを符号表現する多項式の項の個数の最小値のことである.本研究では,n変数ブール関数のPTF密度の最悪時の上界として(0.670)2^nを,平均時の上界として(0.584)2^nを,それぞれ示した.その証明手法は,Oztop(2006)やAmano(2010)による手法をさらに押し進めたもので,線形代数による議論とコンピュータによる計算を組み合わせている.また,この手法を用いた上界改善の限界についても考察する.
- 2011-02-28
著者
関連論文
- グラフ同型問題から環同型問題への新たな帰着 (理論計算機科学の深化と応用)
- Clifford+π/8量子回路の計算能力
- 方形描画(フロアプラン)の個数について:厳密数え上げと下界と上界
- 部分グラフ同型性判定の回路計算量について
- 部分グラフ同型性判定の回路計算量について
- DS-1-3 多項式しきい値関数密度の上界の改善(DS-1.COMP学生シンポジウム,シンポジウムセッション)
- もっとも敏感なk-CNF
- グラフの正方格子上への単位長配置について (アルゴリズムと計算理論の新展開)
- DS-1-7 多項式しきい値関数密度の上界の改善(依頼講演,DS-1.COMP学生シンポジウム,シンポジウムセッション)
- ハッピーエンド問題に対する極値的頂点集合の構造(アルゴリズムとデータ構造・計算複雑度)
- ハッピーエンド問題に対する極値的頂点集合の構造