Pseudo-Boolean function

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

${\displaystyle f:\mathbf {B} ^{n}\to \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 or 1.

Representations

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

${\displaystyle f({\boldsymbol {x}})=a+\sum _{i}a_{i}x_{i}+\sum _{i<j}a_{ij}x_{i}x_{j}+\sum _{i<j<k}a_{ijk}x_{i}x_{j}x_{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 ${\displaystyle f}$ that maps ${\displaystyle \{-1,1\}^{n}}$ to ${\displaystyle \mathbb {R} }$. Again in this case we can uniquely write ${\displaystyle f}$ as a multi-linear polynomial: ${\displaystyle f(x)=\sum _{I\subseteq [n]}{\hat {f}}(I)\prod _{i\in I}x_{i},}$ where ${\displaystyle {\hat {f}}(I)}$ are Fourier coefficients of ${\displaystyle f}$ and ${\displaystyle [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.^[3]

Submodularity

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

${\displaystyle f({\boldsymbol {x}})+f({\boldsymbol {y}})\geq 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. 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 \displaystyle -x_{1}x_{2}x_{3}=\min _{z\in \mathbf {B} }z(2-x_{1}-x_{2}-x_{3})}$

There are other possibilities, for example,

${\displaystyle \displaystyle -x_{1}x_{2}x_{3}=\min _{z\in \mathbf {B} }z(-x_{1}+x_{2}+x_{3})-x_{1}x_{2}-x_{1}x_{3}+x_{1}.}$

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

${\displaystyle \displaystyle f({\boldsymbol {x}})=-2x_{1}+x_{2}-x_{3}+4x_{1}x_{2}+4x_{1}x_{3}-2x_{2}x_{3}-2x_{1}x_{2}x_{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 ${\displaystyle {(0,1,1)}}$).

Polynomial Compression Algorithms

Consider a pseudo-Boolean function ${\displaystyle f}$ as a mapping from ${\displaystyle \{-1,1\}^{n}}$ to ${\displaystyle \mathbb {R} }$. Then ${\displaystyle f(x)=\sum _{I\subseteq [n]}{\hat {f}}(I)\prod _{i\in I}x_{i}.}$ Assume that each coefficient ${\displaystyle {\hat {f}}(I)}$ is integral. Then for an integer ${\displaystyle k}$ the problem P of deciding whether ${\displaystyle f(x)}$ is more or equal to ${\displaystyle 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 ${\displaystyle O(k^{2}\log k).}$ Let ${\displaystyle r}$ be the degree of the above multi-linear polynomial for ${\displaystyle f}$. Then ^[5] proved that in polynomial time we can either solve P or reduce the number of variables to ${\displaystyle 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". Studii și cercetări 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. Boros, E.; Hammer, P. L. (2002). "Pseudo-Boolean Optimization". Discrete Applied Mathematics. 123 (1–3): 155–225. doi:10.1016/S0166-218X(01)00341-9.
4. Kahl, F.; Strandmark, P. (2011). Generalized Roof Duality for Pseudo-Boolean Optimization (PDF). International Conference on Computer Vision.
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. arXiv:1104.1135. Bibcode:2011arXiv1104.1135C.

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. CiteSeerX 10.1.1.675.2183. doi:10.1109/tpami.2010.91. PMID 20421673. S2CID 17314555.
• O'Donnell, Ryan (2008). "Some topics in analysis of Boolean functions". ECCC. ISSN 1433-8092.
• Rother, C.; Kolmogorov, V.; Lempitsky, V.; Szummer, M. (2007). Optimizing Binary MRFs via Extended Roof Duality (PDF). Conference on Computer Vision and Pattern Recognition.
• 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.