Pseudo-Boolean function

In mathematics and optimization, a pseudo-Boolean function is a function of the form : f: \mathbf{B}^n \to \R, where is a Boolean domain and 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.

In mathematics and optimization, a pseudo-Boolean function is a function of the form f: \mathbf{B}^n \to \R, where is a Boolean domain and 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== Any pseudo-Boolean function can be written uniquely as a multi-linear polynomial: f(\boldsymbol{x}) = a + \sum_i a_ix_i + \sum_{i 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 \mathbb{R} . Again in this case we can uniquely write f as a multi-linear polynomial: f(x)= \sum_{I\subseteq [n]}\hat{f}(I)\prod_{i\in I}x_i, where \hat{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. ===Submodularity=== The submodular set functions can be viewed as a special class of pseudo-Boolean functions, which is equivalent to the condition 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\,. 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. 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. ===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 \displaystyle -x_1x_2x_3=\min_{z\in\mathbf{B}}z(2-x_1-x_2-x_3) There are other possibilities, for example, \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. Different reductions lead to different results. Take for example the following cubic polynomial: \displaystyle f(\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)} ). ===Polynomial Compression Algorithms=== Consider a pseudo-Boolean function f as a mapping from \{-1,1\}^n to \mathbb{R} . Then f(x)= \sum_{I\subseteq [n]}\hat{f}(I)\prod_{i\in I}x_i. Assume that each coefficient \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 that in polynomial time we can either solve P or reduce the number of variables to O(k^2\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) . ==See also== Boolean function Quadratic pseudo-Boolean optimization ==Notes== ==References==

Text derived from https://en.wikipedia.org/w/index.php?oldid=1296620603 under CC BY-SA 4.0; modifications have been made.