Pseudo-Boolean function

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

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

where B = {0, 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:

${\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 }$

An important class of pseudo-Boolean functions are the submodular functions, because polynomimal-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 ${\displaystyle f}$ that maps ${\displaystyle \{-1,1\}^{n}}$ to ${\displaystyle \mathbf {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\}}$. For a nice and simple introduction to Fourier analysis of pseudo-Boolean functions, see ^[1].

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

A pseudo-Boolean function f is said to be submodular if

${\displaystyle f({\boldsymbol {x}})+f({\boldsymbol {y}})\geq f({\boldsymbol {x}}\wedge {\boldsymbol {y}})+f({\boldsymbol {x}}\vee {\boldsymbol {y}})}$ 

for every x and y. This is a very importand concept, because a submodular pseudo-boolean function can be minimized in polynomial time.^{[citation needed]}

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

Reductions

If the degree of f is greater than 2, one can always employ reductions to obtain an equivalent quadratic problem with additional variables.^[3] 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:

${\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 \mathbf {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 ^[4] 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 ^[4] 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

References

• Boros (2002). "Pseudo-Boolean Optimization". Discrete Applied Mathematics. 123. doi:10.1016/S0166-218X(01)00341-9. {{cite journal}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)
• Crowston (2011). "Simultaneously Satisfying Linear Equations Over GF(2): MaxLin2 and Max-r-Lin2 Parameterized Above Average". Proc. of FSTTCS 2011. {{cite journal}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)
• Ishsikawa (2011). "Transformation of general binary MRF minimization to the first order case". IEEE Trans. Pattern Analysis and Machine Intelligence. 33 (6): 1234–1249.
• Rother (2007). "Optimizing Binary MRFs via Extended Roof Duality" (PDF). International Conference on Computer Vision and Pattern Recognition. {{cite journal}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)
• O'Donnell (2008). [www.eccc.uni-trier.de/eccc-reports/2008/TR08-055/ "Some topics in analysis of Boolean functions"]. ECCC Report TR08-055. {{cite journal}}: Check |url= value (help); line feed character in |journal= at position 12 (help)

Notes

1. O'Donnell, 2008
2. Boros and Hammer, 2002
3. Ishikawa, 2011
4. Crowston et al., 2011