# Pseudo-Boolean function

In mathematics and optimization, a pseudo-Boolean function is a function of the form
    $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.

## Representations

Any pseudo-Boolean function can be written uniquely as a multi-linear polynomial:
    $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$ 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}})\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. 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_{1}x_{2}x_{3}=\min _{z\in \mathbf {B} }z(2-x_{1}-x_{2}-x_{3})$
There are other possibilities, for example,
    $\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:
    $\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)}$).

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