Abstract
A pseudo-Boolean function is an arbitrary map** 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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
V. L. Beresnev, Discrete Location Problems and Polynomials in Boolean Variables (Inst. Mat. Sib. Otd. Ross. Akad. Nauk, Novosibirsk, 2005) [in Russian].
P. Hammer and S. Rudeanu, “Pseudo-Boolean programming,” Operat. Res. 17 (2), 233–261 (1969).
R. P. Stanley, Enumerative Combinatorics (Cambridge Univ. Press, Cambridge, 1986; Mir, Moscow, 1990).
A. I. Zenkin and V. K. Leont’ev, “On a nonclassical recognition problem,” Comput. Math. Math. Phys. 24 (3), 189–193 (1984).
V. K. Leont’ev, “A theorem on monotone functions,” Diskret. Anal., No. 6, 61–64 (1974).
Author information
Authors and Affiliations
Corresponding author
Additional information
Original Russian Text © V.K. Leont’ev, 2015, published in Zhurnal Vychislitel’noi Matematiki i Matematicheskoi Fiziki, 2015, Vol. 55, No. 11, pp. 1952–1958.
Rights and permissions
About this article
Cite this article
Leont’ev, V.K. On pseudo-Boolean polynomials. Comput. Math. and Math. Phys. 55, 1926–1932 (2015). https://doi.org/10.1134/S0965542515110111
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1134/S0965542515110111