Pseudo-Boolean function: Difference between revisions

Revision as of 20:01, 12 September 2011

Revision as of 20:03, 12 September 2011

Line 30:

===Compression Algorithms===

Consider a pseudo-Boolean function <math> f </math> as a mapping from <math>\{-1,1\}^n</math> to <math>\mathbf{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 of deciding whether <math> f(x)\geq≥ k <\math> is NP-complete. It is proved in <ref name="crow">Crowston et al., 2011</ref>. that

in polynomial time we can either decide whether <math> f(x)\geq ≥ k <\math> or reduce the number of variables to <math> O(k^2\log k) </math>.