Pseudo-Boolean function

Short description: Generalization of binary functions

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

f:𝐁n->ℝ,

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.

## Contents

* 1 Representations
* 2 Optimization
* 2.1 Submodularity
* 2.2 Roof Duality
* 2.3 Quadratizations
* 2.4 Polynomial Compression Algorithms
* 3 See also
* 4 Notes
* 5 References

## Representations

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

f(x)=a+∑iaixi+∑i<jaijxixj+∑i<j<kaijkxixjxk+…

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 ℝ. Again in this case we can uniquely write f as a multi-linear polynomial: f(x)=∑I⊆[n]f^(I)∏i∈Ixi, where 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.[3]

### Submodularity

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

f(x)+f(y)≥f(x∧y)+f(x∨y),∀x,y∈𝐁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

−x1x2x3=minz∈𝐁z(2−x1−x2−x3)

There are other possibilities, for example,

−x1x2x3=minz∈𝐁z(−x1+x2+x3)−x1x2−x1x3+x1.

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

f(x)=−2x1+x2−x3+4x1x2+4x1x3−2x2x3−2x1x2x3.

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 ℝ. Then f(x)=∑I⊆[n]f^(I)∏i∈Ixi. Assume that each coefficient 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(k2log⁡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" (in ro). Studii și cercetări matematice (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. ↑ 3.0 3.1 3.2 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. http://orbi.ulg.ac.be/handle/2268/202427.
4. ↑ Kahl, F.; Strandmark, P. (2011). "Generalized Roof Duality for Pseudo-Boolean Optimization". International Conference on Computer Vision. http://www.maths.lth.se/vision/publdb/reports/pdf/kahl-strandmark-iccv-11.pdf.
5. ↑ 5.0 5.1 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. 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. doi:10.1109/tpami.2010.91. PMID 20421673.
* O'Donnell, Ryan (2008). "Some topics in analysis of Boolean functions". ECCC. ISSN 1433-8092. https://eccc.weizmann.ac.il/report/2008/055/.
* Rother, C.; Kolmogorov, V.; Lempitsky, V.; Szummer, M. (2007). "Optimizing Binary MRFs via Extended Roof Duality". Conference on Computer Vision and Pattern Recognition. http://research.microsoft.com/pubs/67978/cvpr07-QPBOpi.pdf.
* Schrijver, Alexander (November 2000). "A Combinatorial Algorithm Minimizing Submodular Functions in Strongly Polynomial Time". Journal of Combinatorial Theory 80 (2): 346–355. doi:10.1006/jctb.2000.1989.

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Pseudo-Boolean function. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Pseudo-Boolean_function&oldid=4229019"