A pseudo-Boolean function is an arbitrary mapping of the set of binary n-tuples to the real line. Such functions are a natural generalization of classical Boolean functions and find numerous applications in various applied studies. Specifically, the Fourier transform of a Boolean function is a pseudo-Boolean function. A number of facts associated with pseudo-Boolean polynomials are presented, and their applications to well-known discrete optimization problems are described.
展开▼