ブール関数のPTF表現の複雑さについて

概要

論文の詳細を見る
多項式しきい値関数(polynomial threshold function, PTF)とは,プール変数上の多項式pの符号により定義されるプール関数である.PTFのサイズ(密度)とは,pにおける項の個数である.任意のDNF式fは,fのサイズより多項式程度しか大きくならないPTF表現を持つことが知られている.これは,定数個のDNF式を排他的論理和で結んで得られる関数もまた,多項式サイズのPTF表現を持つことを意味している.まず,もし与えられた式f_1[○!+]…[○!+]f_dがXOR-MDNF式,すなわち,すべてのf_iが単調DNF式であり,f_1>‥・>f_dが成り立ち,どの項も2回以上現れない式ならば,そのPTFサイズの上界を改善できることを示す.次に,すべてのn変数プール関数におけるPTFサイズの最大値について考える.O'DonnellとServedioはその上限は(l/2)2^nで抑えられることを予想した.本論文では,計算機実験を行うことで,n=2とn=4のとき彼らに予想に対し否定的な結果を得た.興味深いことに,実験より得られたサイズ(1/2)2^n以下のPTF表現を待たないすべてのプール関数は,2^n個すべてのフーリエ係数の絶対値が同じ値であるという特性を持っていることが分かった.
2004-03-09