# Pseudo-Boolean function

In mathematics and optimization, a **pseudo-Boolean function** is a function of the form

where **B** = {0, 1} is a *Boolean domain* and *n* is a nonnegative integer called the arity of the function. Any pseudo-Boolean function can be written uniquely as a multi-linear polynomial: {{ safesubst:#invoke:Unsubst||date=__DATE__ |$B=
{{#invoke:Category handler|main}}{{#invoke:Category handler|main}}^{[citation needed]}
}}

An important class of pseudo-Boolean functions are the submodular functions, because polynomial-time algorithms exists for minimizing them. The **degree** of the pseudo-Boolean function is simply the degree of the polynomial.

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.^{[1]}

## 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.{{ safesubst:#invoke:Unsubst||date=__DATE__ |$B=
{{#invoke:Category handler|main}}{{#invoke:Category handler|main}}^{[citation needed]}
}}

### Submodularity

A pseudo-Boolean function *f* is said to be **submodular** if

for every * x* and

*. This is a very important concept, because a submodular pseudo-boolean function can be minimized in polynomial time.{{ safesubst:#invoke:Unsubst||date=__DATE__ |$B= {{#invoke:Category handler|main}}{{#invoke:Category handler|main}}*

**y**^{[citation needed]}}}

### 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.^{[2]} 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.^{[2]}

### Reductions

If the degree of *f* is greater than 2, one can always employ *reductions* to obtain an equivalent quadratic problem with additional variables.^{[3]} One possible reduction is

There are other possibilities, for example,

Different reductions lead to different results. Take for example the following cubic polynomial:^{[4]}

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 ^{[5]} 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 ^{[5]} proved that in polynomial time we can either solve P or reduce the number of variables to .

## See also

## References

- {{#invoke:Citation/CS1|citation

|CitationClass=journal }}

- {{#invoke:Citation/CS1|citation

|CitationClass=journal }}

- {{#invoke:Citation/CS1|citation

|CitationClass=journal }}

- {{#invoke:Citation/CS1|citation

|CitationClass=journal }}

- {{#invoke:Citation/CS1|citation

|CitationClass=journal }}

- {{#invoke:Citation/CS1|citation

|CitationClass=journal }}