Content deleted Content added
No edit summary |
No edit summary |
||
Line 3:
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 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.
| |||