RUS  ENG
Full version
JOURNALS // Intelligent systems. Theory and applications // Archive

Intelligent systems. Theory and applications, 2023 Volume 27, Issue 2, Pages 79–82 (Mi ista510)

Part 2. Special Issues in Intellectual Systems Theory

Estimates of the degrees of separating polynomials for monotone and self-dual functions

M. V. Nosov

Lomonosov Moscow State University, Faculty of Mechanics and Mathematics

Abstract: In this paper, we obtain an upper bound on the degree of a polynomial with real coefficients separating zeros and ones of a monotone Boolean function in the odd case of the dimension of space. Together with the previously known estimates for the even case and the lower estimate for the odd one, the final result is obtained. Similar results are obtained for the class of self-dual functions.

Keywords: monotone Boolean function, self-dual Boolean function, separating polynomial.



© Steklov Math. Inst. of RAS, 2025