Pseudo-Boolean function: Difference between revisions

Revision as of 09:46, 8 July 2023

Revision as of 09:49, 8 July 2023

Line 2:

In [[mathematics]] and [[optimization]], a '''pseudo-Boolean function''' is a [[function (mathematics)|function]] of the form

:<math>f: \mathbf{B}^n \to \R,</math>

where {{math|1='''B''' = {{mset|0, 1}}}} is a ''[[Boolean ___domain]]'' and {{mvar|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.

==Representations==

Line 10:

The '''degree''' of the pseudo-Boolean function is simply the degree of the [[polynomial]] in this representation.

In many settings (e.g., in [[Analysis of Boolean functions|Fourier analysis of pseudo-Boolean functions]]), a pseudo-Boolean function is viewed as a function <math>f</math> that maps <math>\{-1,1\}^n</math> to <math>\mathbb{R}</math>. Again in this case we can uniquely write <math>f</math> as a multi-linear polynomial:

<math> f(x)= \sum_{I\subseteq [n]}\hat{f}(I)\prod_{i\in I}x_i, </math> where <math> \hat{f}(I) </math> are Fourier coefficients of <math>f</math> and <math>[n]=\{1,...,n\}</math>.

==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.<ref name="boroshammer" />

===Submodularity===

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

:<math> f(\boldsymbol{x}) + f(\boldsymbol{y}) \ge f(\boldsymbol{x} \wedge \boldsymbol{y}) + f(\boldsymbol{x} \vee \boldsymbol{y}), \; \forall \boldsymbol{x}, \boldsymbol{y}\in \mathbf{B}^n\,. </math>

This is an important class of pseudo-boolean functions, because they can be [[Submodular set function#Submodular Minimization|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.<ref name="boroshammer">Boros and Hammer, 2002</ref> 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.<ref name="boroshammer" />

===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

:<math> \displaystyle -x_1x_2x_3=\min_{z\in\mathbf{B}}z(2-x_1-x_2-x_3) </math>

There are other possibilities, for example,

:<math> \displaystyle -x_1x_2x_3=\min_{z\in\mathbf{B}}z(-x_1+x_2+x_3)-x_1x_2-x_1x_3+x_1. </math>

Different reductions lead to different results. Take for example the following cubic polynomial:<ref name="kahlstrandmark">Kahl and Strandmark, 2011</ref>

:<math> \displaystyle f(\boldsymbol{x})=-2x_1+x_2-x_3+4x_1x_2+4x_1x_3-2x_2x_3-2x_1x_2x_3. </math>

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 <math> {(0,1,1)}</math>).

===Polynomial Compression Algorithms===

Consider a pseudo-Boolean function <math> f </math> as a mapping from <math>\{-1,1\}^n</math> to <math>\mathbb{R}</math>. Then <math> f(x)= \sum_{I\subseteq [n]}\hat{f}(I)\prod_{i\in I}x_i. </math> Assume that each coefficient <math>\hat{f}(I)</math> is integral. Then for an integer <math>k</math> the problem P of deciding whether <math> f(x) </math> is more or equal to <math>k</math> is NP-complete. It is proved in <ref name="crow">Crowston et al., 2011</ref> that in polynomial time we can either solve P or reduce the number of variables to <math> O(k^2\log k).</math> Let <math>r</math> be the degree of the above multi-linear polynomial for <math>f</math>. Then <ref name=crow>Crowston et al., 2011</ref> proved that in polynomial time we can either solve P or reduce the number of variables to <math>r(k-1)</math>.

Then for an integer <math> k </math> the problem P of deciding whether <math> f(x) </math> is more or equal to <math> k </math> is NP-complete. It is proved in <ref name="crow">Crowston et al., 2011</ref> that in polynomial time we can either solve P or reduce the number of variables to <math> O(k^2\log k).</math> Let <math> r </math> be the degree of the above multi-linear polynomial for <math> f </math>. Then <ref name="crow">Crowston et al., 2011</ref> proved that in polynomial time we can either solve P or reduce the number of variables to <math> r(k-1) </math>.

==See also==