Pseudo-Boolean function: Difference between revisions

Revision as of 19:18, 9 February 2021

Revision as of 22:18, 12 February 2021

Line 5:

==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 și cercetări 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 + \cdotsldots</math>

The '''degree''' of the pseudo-Boolean function is simply the degree of the [[polynomial]] in this representation.

In many settings (e.g., in [[Analysis of Boolean functions|Fourier analysis of pseudo-Boolean functions]]), a pseudo-Boolean function is viewed as a function <math>f</math> that maps <math>\{-1,1\}^n</math> to <math>\mathbb{R}</math>. Again in this case we can uniquely write <math>f</math> as a multi-linear polynomial:

<math display="inline"> f(x)= \sum_{I\subseteq [n]}\hat{f}(I)\prod_{i\in I}x_i, </math> where <math> \hat{f}(I) </math> are Fourier coefficients of <math>f</math> and <math>[n]=\{1,\ldots...,n\}</math>.

==Optimization==

Line 40:

===Polynomial Compression Algorithms===

Consider a pseudo-Boolean function {{mvar|<math> f}} </math> as a mapping from {{<math|1={>\{mset|−1-1, 1\}}<sup>''^n''</supmath>}} to <math>\mathbb{R}</math>. Then <math display="inline"> 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 {{mvar|<math> k}} </math> the problem P of deciding whether {{<math|''> f''&hairsp;(''x'')}} </math> is more or equal to {{mvar|<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 {{mvar|<math> r}} </math> be the degree of the above multi-linear polynomial for {{mvar|<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==