Menu
Home Explore People Places Arts History Plants & Animals Science Life & Culture Technology
On this page
Pseudo-Boolean function
Generalization of binary functions

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

f : B n → R , {\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.

We don't have any images related to Pseudo-Boolean function yet.
We don't have any YouTube videos related to Pseudo-Boolean function yet.
We don't have any PDF documents related to Pseudo-Boolean function yet.
We don't have any Books related to Pseudo-Boolean function yet.
We don't have any archived web articles related to Pseudo-Boolean function yet.

Representations

Any pseudo-Boolean function can be written uniquely as a multi-linear polynomial:12

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

f ( x ) + f ( y ) ≥ f ( x ∧ y ) + f ( x ∨ y ) , ∀ x , y ∈ B n . {\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.4 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.5

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

− x 1 x 2 x 3 = min z ∈ B z ( 2 − x 1 − x 2 − x 3 ) {\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,

− x 1 x 2 x 3 = min z ∈ B z ( − x 1 + x 2 + x 3 ) − x 1 x 2 − x 1 x 3 + x 1 . {\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:6

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

Polynomial Compression Algorithms

Consider a pseudo-Boolean function f {\displaystyle f} as a mapping from { − 1 , 1 } n {\displaystyle \{-1,1\}^{n}} to R {\displaystyle \mathbb {R} } . Then f ( x ) = ∑ I ⊆ [ n ] f ^ ( I ) ∏ i ∈ I x i . {\displaystyle f(x)=\sum _{I\subseteq [n]}{\hat {f}}(I)\prod _{i\in I}x_{i}.} Assume that each coefficient f ^ ( I ) {\displaystyle {\hat {f}}(I)} is integral. Then for an integer k {\displaystyle k} the problem P of deciding whether f ( x ) {\displaystyle f(x)} is more or equal to k {\displaystyle k} is NP-complete. It is proved in 7 that in polynomial time we can either solve P or reduce the number of variables to O ( k 2 log ⁡ k ) . {\displaystyle O(k^{2}\log k).} Let r {\displaystyle r} be the degree of the above multi-linear polynomial for f {\displaystyle f} . Then 8 proved that in polynomial time we can either solve P or reduce the number of variables to r ( k − 1 ) {\displaystyle r(k-1)} .

See also

Notes

References

  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. /wiki/ISSN_(identifier) ↩

  2. Hammer, Peter L.; Rudeanu, Sergiu (1968). Boolean Methods in Operations Research and Related Areas. Springer. ISBN 978-3-642-85825-3. 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. hdl:2268/202427. http://orbi.ulg.ac.be/handle/2268/202427 ↩

  4. 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. hdl:2268/202427. http://orbi.ulg.ac.be/handle/2268/202427 ↩

  5. 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. hdl:2268/202427. http://orbi.ulg.ac.be/handle/2268/202427 ↩

  6. Kahl, F.; Strandmark, P. (2011). Generalized Roof Duality for Pseudo-Boolean Optimization (PDF). International Conference on Computer Vision. http://www.maths.lth.se/vision/publdb/reports/pdf/kahl-strandmark-iccv-11.pdf ↩

  7. 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. /wiki/ArXiv_(identifier) ↩

  8. 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. /wiki/ArXiv_(identifier) ↩