Pseudo-Boolean function explained

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

f: B ^{n} \to \R, where is a Boolean domain and 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]}

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 R . Again in this case we can uniquely write f as a multi-linear polynomial:f(x) = \sum _{I\subseteq} \hat{f}(I)\prod _{i\in} x _{i,} where \hat{f}(I) are Fourier coefficients of f and [n] = \{ 1 ,...,n\} .

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.

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 B ^{n.}

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

\displaystyle - x _{1x} _{2x} _{3=min} _{z\inB} z( 2- x _{1-x} _{2-x} _{3)} There are other possibilities, for example,\displaystyle - x _{1x} _{2x} _{3=min} _{z\inB} 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:^[4] \displaystyle f(\boldsymbol{x}) =-2 x _{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 R . Then f(x) = \sum _{I\subseteq} \hat{f}(I)\prod _{i\in} 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 ^[5] that in polynomial time we can either solve P or reduce the number of variables to O(k ^{2log} k). Let r be the degree of the above multi-linear polynomial for f . Then ^[5] proved that in polynomial time we can either solve P or reduce the number of variables to r(k -1 ) .

See also

• Boolean function
• Quadratic pseudo-Boolean optimization

Notes

1. Hammer . P.L. . Rosenberg . I. . Rudeanu . S.. 1963 . On the determination of the minima of pseudo-Boolean functions . ro . Studii și cercetări matematice . 14 . 359–364 . 0039-4068.
2. Book: Hammer . Peter L. . Rudeanu . Sergiu . 1968 . Boolean Methods in Operations Research and Related Areas . Springer . 978-3-642-85825-3.
3. Boros . E. . Hammer . P. L. . 2002 . Pseudo-Boolean Optimization . . 10.1016/S0166-218X(01)00341-9 . free . 123 . 1–3 . 155–225 .
4. Kahl . F. . Strandmark . P. . 2011. Generalized Roof Duality for Pseudo-Boolean Optimization . .
5. Crowston . R. . Fellows . M. . Gutin . G. . Jones . M. . Rosamond . F. . Thomasse . S. . Yeo . A. . 2011 . Simultaneously Satisfying Linear Equations Over GF(2): MaxLin2 and Max-r-Lin2 Parameterized Above Average. . Proc. Of FSTTCS 2011 . 1104.1135 . 2011arXiv1104.1135C.

References

• Ishikawa . H. . 2011 . Transformation of general binary MRF minimization to the first order case . . 10.1109/tpami.2010.91 . 20421673 . 10.1.1.675.2183 . 17314555 . 33 . 6 . 1234–1249.
• O'Donnell . Ryan . Ryan O'Donnell (computer scientist). 2008 . Some topics in analysis of Boolean functions . ECCC . 1433-8092 .
• Rother . C. . Kolmogorov . V. . Lempitsky . V. . Szummer . M. . 2007 . Optimizing Binary MRFs via Extended Roof Duality . .
• Schrijver . Alexander . November 2000 . A Combinatorial Algorithm Minimizing Submodular Functions in Strongly Polynomial Time . Journal of Combinatorial Theory . B . 10.1006/jctb.2000.1989 . 80 . 2 . 346–355. free .