DS-1-3 多項式しきい値関数密度の上界の改善(DS-1.COMP学生シンポジウム,シンポジウムセッション)

• 早坂 智行

  東京工業大学大学院情報理工学研究科数理・計算科学専攻

• 天野 一幸

  群馬大学大学院工学研究科情報工学専攻

書誌事項

タイトル別名

• DS-1-3 Improved Upper Bounds on PTF Density of Boolean Functions

抄録

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 (1), "S-5"-"S-6", 2011-02-28

  一般社団法人電子情報通信学会

詳細情報

• CRID: 1571698601979038592
• NII論文ID: 110008574255
• NII書誌ID: AN10471452
• 本文言語コード: ja
• データソース種別:
  • CiNii Articles