Pseudo-Boolean function: Difference between revisions

Revision as of 12:56, 12 February 2012

Revision as of 22:05, 12 December 2012

Line 1:

In [[mathematics]] and [[optimization]], a '''pseudo-Boolean function''' is a [[function (mathematics)|function]] of the form

:<math>f:\mathbf{B}^n \rightarrow \mathbfmathbb{R}</math>,

where '''B'''&nbsp;=&nbsp;{0,&nbsp;1} is a ''[[Boolean ___domain]]'' and ''n'' is a nonnegative integer called the [[arity]] of the function. Any pseudo-Boolean function can be written uniquely as a [[multi-linear]] polynomial:

:<math>f(\boldsymbol{x}) = a + \sum_i a_ix_i + \sum_{i<j}a_{ij}x_ix_j + \sum_{i<j<k}a_{ijk}x_ix_jx_k + \ldots</math>

An important class of pseudo-Boolean functions are the [[supermodular function|submodular functions]], because polynomial-time algorithms exists for minimizing them. The '''degree''' of the pseudo-Boolean function is simply the degree of the polynomial.

In many settings (e.g., in Fourier analysis of pseudo-Boolean functions), a pseudo-Boolean function is viewed as a function <math>f</math> that maps <math>\{-1,1\}^n</math> to <math>\mathbfmathbb{R}</math>. Again in this case we can uniquely write <math>f</math> as a multi-linear polynomial:

<math> f(x)= \sum_{I\subseteq [n]}\hat{f}(I)\prod_{i\in I}x_i, </math> where <math> \hat{f}(I) </math> are Fourier coefficients of <math>f</math> and <math>[n]=\{1,...,n\}</math>. For a nice and simple introduction to Fourier analysis of pseudo-Boolean functions, see <ref name="odon">O'Donnell, 2008</ref>.

Line 30:

===Polynomial Compression Algorithms===

Consider a pseudo-Boolean function <math> f </math> as a mapping from <math>\{-1,1\}^n</math> to <math>\mathbfmathbb{R}</math>. Then <math> f(x)= \sum_{I\subseteq [n]}\hat{f}(I)\prod_{i\in I}x_i. </math> Assume that each coefficient <math>\hat{f}(I)</math> is integral.

Then for an integer <math> k </math> the problem P of deciding whether <math> f(x) </math> is more or equal to <math> k </math> is NP-complete. It is proved in <ref name="crow">Crowston et al., 2011</ref> that

in polynomial time we can either solve P or reduce the number of variables to <math> O(k^2\log k) </math>.