# Pseudo-Boolean function

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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

$f:\mathbf {B} ^{n}\rightarrow \mathbb {R}$ ,

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] }} $f({\boldsymbol {x}})=a+\sum _{i}a_{i}x_{i}+\sum _{i 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. ## 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

$f({\boldsymbol {x}})+f({\boldsymbol {y}})\geq f({\boldsymbol {x}}\wedge {\boldsymbol {y}})+f({\boldsymbol {x}}\vee {\boldsymbol {y}})$ for every x and y. 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}}[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. 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.

### Reductions

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