Pseudo-Boolean function

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In mathematics and optimization, a pseudo-Boolean function is a function of the form

,

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,1.

Representations[edit]

Any pseudo-Boolean function can be written uniquely as a multi-linear polynomial:[1][2]

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

In many settings (e.g., in Fourier analysis of pseudo-Boolean functions), a pseudo-Boolean function is viewed as a function that maps to . Again in this case we can uniquely write as a multi-linear polynomial: where are Fourier coefficients of and . For a nice and simple introduction to Fourier analysis of pseudo-Boolean functions, see.[3]

Optimization[edit]

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.[4]

Submodularity[edit]

The submodular set functions can be viewed as a special class of pseudo-Boolean functions, which is equivalent to the condition

This is an important class of pseudo-boolean functions, because they can be minimized in polynomial time.

Roof Duality[edit]

If f is a quadratic polynomial, a concept called roof duality can be used to obtain a lower bound for its minimum value.[4] Roof duality may also provide a partial assignment of the variables, indicating some of the values of a minimizer to the polynomial. Several different methods of obtaining lower bounds were developed only to later be shown to be equivalent to what is now called roof duality.[4]

Reductions[edit]

If the degree of f is greater than 2, one can always employ reductions to obtain an equivalent quadratic problem with additional variables.[5] One possible reduction is

There are other possibilities, for example,

Different reductions lead to different results. Take for example the following cubic polynomial:[6]

Using the first reduction followed by roof duality, we obtain a lower bound of -3 and no indication on how to assign the three variables. Using the second reduction, we obtain the (tight) lower bound of -2 and the optimal assignment of every variable (which is ).

Polynomial Compression Algorithms[edit]

Consider a pseudo-Boolean function as a mapping from to . Then Assume that each coefficient is integral. Then for an integer the problem P of deciding whether is more or equal to is NP-complete. It is proved in [7] that in polynomial time we can either solve P or reduce the number of variables to . Let be the degree of the above multi-linear polynomial for . Then [7] proved that in polynomial time we can either solve P or reduce the number of variables to .

See also[edit]

References[edit]

Notes[edit]

  1. ^ Hammer, P.L.; Rosenberg, I.; Rudeanu, S. (1963). "On the determination of the minima of pseudo-Boolean functions". Studii ¸si cercetari matematice (in Romanian) (14): 359–364. ISSN 0039-4068. 
  2. ^ Hammer, Peter L.; Rudeanu, Sergiu (1968). Boolean Methods in Operations Research and Related Areas. Springer. ISBN 978-3-642-85825-3. 
  3. ^ O'Donnell, 2008
  4. ^ a b c Boros and Hammer, 2002
  5. ^ Ishikawa, 2011
  6. ^ Kahl and Strandmark, 2011
  7. ^ a b Crowston et al., 2011