Pseudo-Boolean function: Difference between revisions

Revision as of 01:11, 13 March 2011

Revision as of 14:30, 3 August 2011

Line 1:

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

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

where '''B'''&nbsp;=&nbsp;{0,&nbsp;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:

:<math>f(\boldsymbol{x}) = a + \sum_i a_ix_i + \sum_{i<j}a_{ij}x_ix_j + \sum_{i<j<k}a_{ijk}x_ix_jx_k + \ldots</math>

An important class of pseudo-Boolean functions are the [[supermodular function|submodular functions]], because polynomimal-time algorithms exists for minimizing them.

==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. The '''degree''' of the pseudo-Boolean function is simply the degree of the polynomial.

===Reductions===