情報処理学会 第73回全国大会講演要旨

{1, -1}上のn変数ブール関数fと実数上のn変数多項式pについて，
任意の入力xでsgn(p(x))=f(x)が成立しているとき，
fはpにより符号表現されているという．
ブール関数fの多項式しきい値関数密度(PTF密度)とは，
fを符号表現する多項式の項の個数の最小値のことである．
本研究では，平均時と最悪時それぞれのPTF密度について新たな上界を与える．
その証明手法は，Oztop[Neural Networks, 2006]や
Amano[ISAAC'10]による手法をさらに押し進めたもので，
線形代数による議論とコンピュータによる計算を組み合わせている．
また，この手法を用いた上界改善の限界についても考察する．