Pseudo-Boolean function: Difference between revisions

Revision as of 23:04, 18 October 2019

Revision as of 18:46, 13 December 2019

Line 5:

==Representations==

Any pseudo-Boolean function can be written uniquely as a [[multi-linear]] polynomial:<ref>{{Cite journal|url = |title = On the determination of the minima of pseudo-Boolean functions|last = Hammer|first = P.L.|date = 1963|journal = Studii ¸si Cercetari Matematice|doi = |pmid = |access-date = |last2 = Rosenberg|first2 = I.|last3 = Rudeanu|first3 = S.|issue = 14|publisher = |pages = 359–364|language = Romanian|issn = 0039-4068}}</ref><ref>{{Cite book|title = Boolean Methods in Operations Research and Related Areas|last = Hammer|first = Peter L.|publisher = Springer|year = 1968|isbn = 978-3-642-85825-3|___location = |pages = |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.