Pseudo-Boolean function

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

[math]\displaystyle{ f: \mathbf{B}^n \to \R, }[/math]

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 or 1.

Representations

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

[math]\displaystyle{ f(\boldsymbol{x}) = a + \sum_i a_ix_i + \sum_{i\lt j}a_{ij}x_ix_j + \sum_{i\lt j\lt k}a_{ijk}x_ix_jx_k + \ldots }[/math]

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 [math]\displaystyle{ f }[/math] that maps [math]\displaystyle{ \{-1,1\}^n }[/math] to [math]\displaystyle{ \mathbb{R} }[/math]. Again in this case we can uniquely write [math]\displaystyle{ f }[/math] as a multi-linear polynomial: [math]\displaystyle{ f(x)= \sum_{I\subseteq [n]}\hat{f}(I)\prod_{i\in I}x_i, }[/math] where [math]\displaystyle{ \hat{f}(I) }[/math] are Fourier coefficients of [math]\displaystyle{ f }[/math] and [math]\displaystyle{ [n]=\{1,...,n\} }[/math].

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.^[3]

Submodularity

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

[math]\displaystyle{ 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\,. }[/math]

This is an important class of pseudo-boolean functions, because they can be minimized in polynomial time. Note that minimization of a submodular function is a polynomially solvable problem independent on the presentation form, for e.g. pesudo-Boolean polynomials, opposite to maximization of a submodular function which is NP-hard, Alexander Schrijver (2000).

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.^[3] 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.^[3]

Quadratizations

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

[math]\displaystyle{ \displaystyle -x_1x_2x_3=\min_{z\in\mathbf{B}}z(2-x_1-x_2-x_3) }[/math]

There are other possibilities, for example,

[math]\displaystyle{ \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. }[/math]

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

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

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 [math]\displaystyle{ {(0,1,1)} }[/math]).

Polynomial Compression Algorithms

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

See also

• Boolean function
• Quadratic pseudo-Boolean optimization

Notes

References

• Ishikawa, H. (2011). "Transformation of general binary MRF minimization to the first order case". IEEE Transactions on Pattern Analysis and Machine Intelligence 33 (6): 1234–1249. doi:10.1109/tpami.2010.91. PMID 20421673. 
• O'Donnell, Ryan (2008). "Some topics in analysis of Boolean functions". ECCC. ISSN 1433-8092. https://eccc.weizmann.ac.il/report/2008/055/. 
• Rother, C.; Kolmogorov, V.; Lempitsky, V.; Szummer, M. (2007). "Optimizing Binary MRFs via Extended Roof Duality". Conference on Computer Vision and Pattern Recognition. http://research.microsoft.com/pubs/67978/cvpr07-QPBOpi.pdf. 
• Schrijver, Alexander (November 2000). "A Combinatorial Algorithm Minimizing Submodular Functions in Strongly Polynomial Time". Journal of Combinatorial Theory. B 80 (2): 346-355. doi:10.1006/jctb.2000.1989. 

0.00 (0 votes) Original source: https://en.wikipedia.org/wiki/Pseudo-Boolean function. Read more