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 that maps to . Again in this case we can uniquely write as a multi-linear polynomial: where are Fourier coefficients of and . For a nice and simple introduction to Fourier analysis of pseudo-Boolean functions, see.
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.
The submodular set functions can be viewed as a special class of pseudo-Boolean functions, which is equivalent to the condition
This is an important class of pseudo-boolean functions, because they can be minimized in polynomial time.
If f is a quadratic polynomial, a concept called roof duality can be used to obtain a lower bound for its minimum value. 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.
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
There are other possibilities, for example,
Different reductions lead to different results. Take for example the following cubic polynomial:
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 ).
Polynomial Compression Algorithms
Consider a pseudo-Boolean function as a mapping from to . Then Assume that each coefficient is integral. Then for an integer the problem P of deciding whether is more or equal to is NP-complete. It is proved in  that in polynomial time we can either solve P or reduce the number of variables to . Let be the degree of the above multi-linear polynomial for . Then  proved that in polynomial time we can either solve P or reduce the number of variables to .
- Boros; Hammer (2002). "Pseudo-Boolean Optimization". Discrete Applied Mathematics. 123. doi:10.1016/S0166-218X(01)00341-9.
- Crowston; Fellows, Gutin; Jones, Rosamond; Thomasse, Yeo (2011). "Simultaneously Satisfying Linear Equations Over GF(2): MaxLin2 and Max-r-Lin2 Parameterized Above Average.". Proc. of FSTTCS 2011. arXiv: .
- Ishikawa (2011). "Transformation of general binary MRF minimization to the first order case". IEEE Trans. Pattern Analysis and Machine Intelligence. 33 (6): 1234–1249. doi:10.1109/tpami.2010.91.
- Rother; Kolmogorov; Lempitsky; Szummer (2007). "Optimizing Binary MRFs via Extended Roof Duality" (PDF). International Conference on Computer Vision and Pattern Recognition.
- Kahl; Strandmark (2011). "Generalized Roof Duality for Pseudo-Boolean Optimization" (PDF). International Conference on Computer Vision.
- O'Donnell, Ryan (2008). "Some topics in analysis of Boolean functions". ECCC TR08-055. External link in
- Hammer, P.L.; Rosenberg, I.; Rudeanu, S. (1963). "On the determination of the minima of pseudo-Boolean functions". Studii ¸si cercetari matematice (in Romanian) (14): 359–364. ISSN 0039-4068.
- Hammer, Peter L.; Rudeanu, Sergiu (1968). Boolean Methods in Operations Research and Related Areas. Springer. ISBN 978-3-642-85825-3.
- O'Donnell, 2008
- Boros and Hammer, 2002
- Ishikawa, 2011
- Kahl and Strandmark, 2011
- Crowston et al., 2011