Part 2. Special Issues in Intellectual Systems Theory

Degrees of separating polynomials for Post’s classes

M. V. Nosov

Lomonosov Moscow State University, Faculty of Mechanics and Mathematics

Abstract: In this paper, estimates of the degrees of polynomials with real coeficients separating zeros and ones of Boolean functions for Post’s classes are obtained.

Keywords: Post’s classes, separating polynomial