Pseudo-Boolean function

Any pseudo-Boolean function can be written uniquely as a multi-linear polynomial:{{cite journal |last1=Hammer |first1=P.L. |last2=Rosenberg |first2=I. |last3=Rudeanu |first3=S.|date=1963 |title=On the determination of the minima of pseudo-Boolean functions |language=ro |journal=Studii și cercetări matematice |issue=14 |pages=359–364 |issn=0039-4068}}{{cite book |last1=Hammer |first1=Peter L. |last2=Rudeanu |first2=Sergiu |year=1968 |title=Boolean Methods in Operations Research and Related Areas |publisher=Springer |isbn=978-3-642-85825-3}}

:

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 $\backslash \{-1,1\backslash \}^n$ to $\backslash mathbb\{R\}$. Again in this case we can uniquely write $f$ as a multi-linear polynomial:

$f(x)=\; \backslash sum\_\{I\backslash subseteq\; [n]\}\backslash hat\{f\}(I)\backslash prod\_\{i\backslash in\; I\}x\_i,$ where $\backslash hat\{f\}(I)$ are Fourier coefficients of $f$ and $[n]=\backslash \{1,...,n\backslash \}$.

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

:$f(\backslash boldsymbol\{x\})\; +\; f(\backslash boldsymbol\{y\})\; \backslash ge\; f(\backslash boldsymbol\{x\}\; \backslash wedge\; \backslash boldsymbol\{y\})\; +\; f(\backslash boldsymbol\{x\}\; \backslash vee\; \backslash boldsymbol\{y\}),\; \backslash ;\; \backslash forall\; \backslash boldsymbol\{x\},\; \backslash boldsymbol\{y\}\backslash in\; \backslash mathbf\{B\}^n\backslash ,.$

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

If f is a quadratic polynomial, a concept called roof duality can be used to obtain a lower bound for its minimum value.{{cite journal |last1=Boros |first1=E. |last2=Hammer |first2=P. L. |year=2002 |title=Pseudo-Boolean Optimization |journal=Discrete Applied Mathematics |doi=10.1016/S0166-218X(01)00341-9 |doi-access=free |volume=123 |issue=1–3 |pages=155–225 |hdl=2268/202427 |url=http://orbi.ulg.ac.be/handle/2268/202427|hdl-access=free }} 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

:$\backslash displaystyle\; -x\_1x\_2x\_3=\backslash min\_\{z\backslash in\backslash mathbf\{B\}\}z(2-x\_1-x\_2-x\_3)$

There are other possibilities, for example,

:$\backslash displaystyle\; -x\_1x\_2x\_3=\backslash min\_\{z\backslash in\backslash mathbf\{B\}\}z(-x\_1+x\_2+x\_3)-x\_1x\_2-x\_1x\_3+x\_1.$

Different reductions lead to different results. Take for example the following cubic polynomial:{{cite conference |last1=Kahl |first1=F. |last2=Strandmark |first2=P. |year=2011|title=Generalized Roof Duality for Pseudo-Boolean Optimization |conference=International Conference on Computer Vision |url=http://www.maths.lth.se/vision/publdb/reports/pdf/kahl-strandmark-iccv-11.pdf}}

:$\backslash displaystyle\; f(\backslash boldsymbol\{x\})=-2x\_1+x\_2-x\_3+4x\_1x\_2+4x\_1x\_3-2x\_2x\_3-2x\_1x\_2x\_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)\}$).

Consider a pseudo-Boolean function $f$ as a mapping from $\backslash \{-1,1\backslash \}^n$ to $\backslash mathbb\{R\}$. Then $f(x)=\; \backslash sum\_\{I\backslash subseteq\; [n]\}\backslash hat\{f\}(I)\backslash prod\_\{i\backslash in\; I\}x\_i.$ Assume that each coefficient $\backslash hat\{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 {{cite journal |last1=Crowston |first1=R. |last2=Fellows |first2=M. |last3=Gutin |first3=G. |last4=Jones |first4=M. |last5=Rosamond |first5=F. |last6=Thomasse |first6=S. |last7=Yeo |first7=A. |year=2011 |title=Simultaneously Satisfying Linear Equations Over GF(2): MaxLin2 and Max-r-Lin2 Parameterized Above Average. |journal=Proc. Of FSTTCS 2011 |arxiv=1104.1135 |bibcode=2011arXiv1104.1135C}} that in polynomial time we can either solve P or reduce the number of variables to $O(k^2\backslash log\; k).$ Let $r$ be the degree of the above multi-linear polynomial for $f$. Then proved that in polynomial time we can either solve P or reduce the number of variables to $r(k-1)$.

• Boolean function
• Quadratic pseudo-Boolean optimization

• {{cite journal |last=Ishikawa |first=H. |year=2011 |title=Transformation of general binary MRF minimization to the first order case |journal=IEEE Transactions on Pattern Analysis and Machine Intelligence |doi=10.1109/tpami.2010.91 |pmid=20421673 |citeseerx=10.1.1.675.2183 |s2cid=17314555 |volume=33 |number=6 |pages=1234–1249}}
• {{cite journal |last=O'Donnell |first=Ryan | author-link = Ryan O'Donnell (computer scientist)|year=2008 |title=Some topics in analysis of Boolean functions |journal=ECCC |issn=1433-8092 |url=https://eccc.weizmann.ac.il/report/2008/055/}}
• {{cite conference |last1=Rother |first1=C. |last2=Kolmogorov |first2=V. |last3=Lempitsky |first3=V. |last4=Szummer |first4=M. |year=2007 |title=Optimizing Binary MRFs via Extended Roof Duality |conference=Conference on Computer Vision and Pattern Recognition |url=http://research.microsoft.com/pubs/67978/cvpr07-QPBOpi.pdf}}
• {{cite journal |last=Schrijver |first=Alexander |date=November 2000 |title=A Combinatorial Algorithm Minimizing Submodular Functions in Strongly Polynomial Time |journal=Journal of Combinatorial Theory |doi=10.1006/jctb.2000.1989 |volume=80 |issue=2 |pages=346–355|doi-access=free }}

Category:Mathematical optimization