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.

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)