Pseudo-Boolean function

In mathematics and optimization, a pseudo-Boolean function is a function of the form

$f:\mathbf{B}^n \rightarrow \mathbb{R}$,

where B = {0, 1} is a Boolean domain and n is a nonnegative integer called the arity of the function. A Boolean function is then a special case, where the values are also restricted to 0,1.

Representations

Any pseudo-Boolean function can be written uniquely as a multi-linear polynomial: ^[1][2]

$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$

The degree of the pseudo-Boolean function is simply the degree of the polynomial in this representation.

In many settings (e.g., in Fourier analysis of pseudo-Boolean functions), a pseudo-Boolean function is viewed as a function $f$ that maps $\{-1,1\}^n$ to $\mathbb{R}$. Again in this case we can uniquely write $f$ as a multi-linear polynomial: $f(x)= \sum_{I\subseteq [n]}\hat{f}(I)\prod_{i\in I}x_i,$ where $\hat{f}(I)$ are Fourier coefficients of $f$ and $[n]=\{1,...,n\}$. For a nice and simple introduction to Fourier analysis of pseudo-Boolean functions, see.^[3]

Optimization

Minimizing (or, equivalently, maximizing) a pseudo-Boolean function is NP-hard. This can easily be seen by formulating, for example, the maximum cut problem as maximizing a pseudo-Boolean function.^[4]

Submodularity

The submodular set functions can be viewed as a special class of pseudo-Boolean functions, which is equivalent to the condition

$f(\boldsymbol{x}) + f(\boldsymbol{y}) \ge f(\boldsymbol{x} \wedge \boldsymbol{y}) + f(\boldsymbol{x} \vee \boldsymbol{y}), \; \forall \boldsymbol{x}, \boldsymbol{y}\in \mathbf{B}^n\,.$

This is an important class of pseudo-boolean functions, because they can be minimized in polynomial time.

Roof Duality

If f is a quadratic polynomial, a concept called roof duality can be used to obtain a lower bound for its minimum value.^[4] Roof duality may also provide a partial assignment of the variables, indicating some of the values of a minimizer to the polynomial. Several different methods of obtaining lower bounds were developed only to later be shown to be equivalent to what is now called roof duality.^[4]

Reductions

If the degree of f is greater than 2, one can always employ reductions to obtain an equivalent quadratic problem with additional variables.^[5] One possible reduction is

$\displaystyle -x_1x_2x_3=\min_{z\in\mathbf{B}}z(2-x_1-x_2-x_3)$

There are other possibilities, for example,

$\displaystyle -x_1x_2x_3=\min_{z\in\mathbf{B}}z(-x_1+x_2+x_3)-x_1x_2-x_1x_3+x_1.$

Different reductions lead to different results. Take for example the following cubic polynomial:^[6]

$\displaystyle f(\boldsymbol{x})=-2x_1+x_2-x_3+4x_1x_2+4x_1x_3-2x_2x_3-2x_1x_2x_3.$

Using the first reduction followed by roof duality, we obtain a lower bound of -3 and no indication on how to assign the three variables. Using the second reduction, we obtain the (tight) lower bound of -2 and the optimal assignment of every variable (which is ${(0,1,1)}$).

Polynomial Compression Algorithms

Consider a pseudo-Boolean function $f$ as a mapping from $\{-1,1\}^n$ to $\mathbb{R}$. Then $f(x)= \sum_{I\subseteq [n]}\hat{f}(I)\prod_{i\in I}x_i.$ Assume that each coefficient $\hat{f}(I)$ is integral. Then for an integer $k$ the problem P of deciding whether $f(x)$ is more or equal to $k$ is NP-complete. It is proved in ^[7] that in polynomial time we can either solve P or reduce the number of variables to $O(k^2\log k)$. Let $r$ be the degree of the above multi-linear polynomial for $f$. Then ^[7] proved that in polynomial time we can either solve P or reduce the number of variables to $r(k-1)$.

See also

• Boolean function

References

• Boros; Hammer (2002). "Pseudo-Boolean Optimization". Discrete Applied Mathematics 123. doi:10.1016/S0166-218X(01)00341-9.
• Crowston; Fellows, Gutin; Jones, Rosamond; Thomasse, Yeo (2011). "Simultaneously Satisfying Linear Equations Over GF(2): MaxLin2 and Max-r-Lin2 Parameterized Above Average.". Proc. of FSTTCS 2011.
• Ishikawa (2011). "Transformation of general binary MRF minimization to the first order case". IEEE Trans. Pattern Analysis and Machine Intelligence 33 (6): 1234–1249. doi:10.1109/tpami.2010.91.
• Rother; Kolmogorov; Lempitsky; Szummer (2007). "Optimizing Binary MRFs via Extended Roof Duality" (PDF). International Conference on Computer Vision and Pattern Recognition.
• Kahl; Strandmark (2011). "Generalized Roof Duality for Pseudo-Boolean Optimization" (PDF). International Conference on Computer Vision.
• O'Donnell, Ryan (2008). "Some topics in analysis of Boolean functions". ECCC TR08-055.

Notes

1. Hammer, P.L.; Rosenberg, I.; Rudeanu, S. (1963). "On the determination of the minima of pseudo-Boolean functions". Studii ¸si cercetari matematice (in Romanian) (14): 359–364. ISSN 0039-4068.
2. Hammer, Peter L.; Rudeanu, Sergiu (1968). Boolean Methods in Operations Research and Related Areas. Springer. ISBN 978-3-642-85825-3.
3. O'Donnell, 2008
4. Boros and Hammer, 2002
5. Ishikawa, 2011
6. Kahl and Strandmark, 2011
7. Crowston et al., 2011