Article collection "Mathematical Problems of Cybernetics" №20, Moscow, 2022
Authors:Chukhrov I.P.
Boolean functions minimization problem: conditions of minimality and the probabilistic method
Abstract:
The article is written on the basis of reports presented at the XII International Seminar. Discrete mathematics and its applications named after academician O. B. Lupanov (Moscow, Moscow State University, June 20–25, 2016) and contains a survey of results for the problem of minimizing Boolean functions, in which methods are considered for proving the minimality and nonconstructive approaches to obtaining estimates of parameters that characterize the complexity of minimization with respect to classes of measures difficulties.
Keywords:
minimization of boolean functions, n-dimensional unit cube, face, complex of faces, cover, measure of complexity, kernel, irredundant, shortest, minimum cover, lower bound for cover complexity
Publication language:russian, pages:18 (p. 7-24)
Research direction:
Mathematical problems and theory of numerical methods
