DS-1-7 多項式しきい値関数密度の上界の改善(依頼講演,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)による手法をさらに押し進めたもので,線形代数による議論とコンピュータによる計算を組み合わせている.また,この手法を用いた上界改善の限界についても考察する.
- 2012-03-06
著者
関連論文
- グラフ同型問題から環同型問題への新たな帰着 (理論計算機科学の深化と応用)
- DS-1-3 多項式しきい値関数密度の上界の改善(DS-1.COMP学生シンポジウム,シンポジウムセッション)
- DS-1-7 多項式しきい値関数密度の上界の改善(依頼講演,DS-1.COMP学生シンポジウム,シンポジウムセッション)