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

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.

Reductions

Roof Duality

See also

• Boolean function

References

• Boros (2002). "Pseudo-Boolean Optimization". Discrete Applied Mathematics. {{cite journal}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)
• 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)