Content deleted Content added
m a) "0 or 1" ok (I considered "0 and 1" or just adding a space "0, 1")? b) "Studii ¸si" seemed like a typo, comma in wrong place, but is a transliteration from Romanian. Rather keep "Studii ¸si Cercetari Matematice"? I also see "Studii si cercetari matematice" as possible transliteration, while any transliteration doesn't seem too helpful. |
|||
Line 1:
In [[mathematics]] and [[optimization]], a '''pseudo-Boolean function''' is a [[function (mathematics)|function]] of the form
:<math>f:\mathbf{B}^n \rightarrow \mathbb{R}</math>,
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
==Representations==
Any pseudo-Boolean function can be written uniquely as a [[multi-linear]] polynomial:<ref>{{Cite journal|title = On the determination of the minima of pseudo-Boolean functions|last1 = Hammer|first1 = P.L.|date = 1963|journal = Studii
▲Any pseudo-Boolean function can be written uniquely as a [[multi-linear]] polynomial:<ref>{{Cite journal|title = On the determination of the minima of pseudo-Boolean functions|last1 = Hammer|first1 = P.L.|date = 1963|journal = Studii ¸si Cercetari Matematice|last2 = Rosenberg|first2 = I.|last3 = Rudeanu|first3 = S.|issue = 14|pages = 359–364|language = ro|issn = 0039-4068}}</ref><ref>{{Cite book|title = Boolean Methods in Operations Research and Related Areas|last1 = Hammer|first1 = Peter L.|publisher = Springer|year = 1968|isbn = 978-3-642-85825-3|last2 = Rudeanu|first2 = Sergiu}}</ref>
:<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>
The '''degree''' of the pseudo-Boolean function is simply the degree of the [[polynomial]] in this representation.
Line 18:
The [[submodular set function]]s can be viewed as a special class of pseudo-Boolean functions, which is equivalent to the condition
:<math> f(\boldsymbol{x}) + f(\boldsymbol{y}) \ge f(\boldsymbol{x} \wedge \boldsymbol{y}) + f(\boldsymbol{x} \vee \boldsymbol{y}), \; \forall \boldsymbol{x}, \boldsymbol{y}\in \mathbf{B}^n\,. </math>
This is an important class of pseudo-boolean functions, because they can be [[Submodular set function#Submodular Minimization|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===
Line 25:
===Quadratizations===
If the degree of ''f'' is greater than 2, one can always employ ''reductions'' to obtain an equivalent quadratic problem with additional variables. An open source book on the subject, mainly written by [[Nike Dattani]], contains dozens of different quadratization methods.<ref name="dattani">{{citation
| last1 = Dattani | first1 = N.
| title = Quadratization in discrete optimization and quantum mechanics
| date = 2019-01-14| arxiv = 1901.04405
}}</ref>
One possible reduction is
:<math> \displaystyle -x_1x_2x_3=\min_{z\in\mathbf{B}}z(2-x_1-x_2-x_3) </math>
There are other possibilities, for example,
:<math> \displaystyle -x_1x_2x_3=\min_{z\in\mathbf{B}}z(-x_1+x_2+x_3)-x_1x_2-x_1x_3+x_1. </math>
Line 42 ⟶ 41:
===Polynomial Compression Algorithms===
Consider a pseudo-Boolean function <math> f </math> as a mapping from <math>\{-1,1\}^n</math> to <math>\mathbb{R}</math>. Then <math> f(x)= \sum_{I\subseteq [n]}\hat{f}(I)\prod_{i\in I}x_i. </math> Assume that each coefficient <math>\hat{f}(I)</math> is integral.
Then for an integer <math> k </math> the problem P of deciding whether <math> f(x) </math> is more or equal to <math> k </math> is NP-complete. It is proved in <ref name="crow">Crowston et al., 2011</ref> that in polynomial time we can either solve P or reduce the number of variables to <math> O(k^2\log k).</math> Let <math> r </math> be the degree of the above multi-linear polynomial for <math> f </math>. Then <ref name="crow">Crowston et al., 2011</ref> proved that in polynomial time we can either solve P or reduce the number of variables to <math> r(k-1) </math>.
==See also==
| |||