Anzeige
Erschienen in:
2010 | OriginalPaper | Buchkapitel
New Upper Bounds on the Average PTF Density of Boolean Functions
verfasst von : Kazuyuki Amano
Erschienen in: Algorithms and Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
A Boolean function
f
:{1, − 1}
n
→{1, − 1} is said to be sign-represented by a real polynomial
$p:{\mathbb R}^n \rightarrow {\mathbb R}$
if sgn(
p
(
x
)) =
f
(
x
) for all
x
∈ {1, − 1}
n
. The PTF density of
f
is the minimum number of monomials in a polynomial that sign-represents
f
. It is well known that every
n
-variable Boolean function has PTF density at most 2
n
. However, in general, less monomials are enough. In this paper, we present a method that reduces the problem of upper bounding the average PTF density of
n
-variable Boolean functions to the computation of (some modified version of) average PTF density of
k
-variable Boolean functions for small
k
. By using this method, we show that almost all
n
-variable Boolean functions have PTF density at most (0.617) 2
n
, which is the best upper bound so far.