RUS  ENG
Full version
JOURNALS // Diskretnaya Matematika // Archive

Diskr. Mat., 1993 Volume 5, Issue 2, Pages 111–115 (Mi dm682)

This article is cited in 5 papers

Complexity of Boolean functions in the class of canonical polarized polynomials

V. P. Suprun


Abstract: A canonical polarized polynomial of a Boolean function $F$ in $n$ variables is a polynomial where one part of the variables of the function $F$ enters the summands only with negation and the second part only without negation. By the complexity of function $F$ in a class of canonical polarized polynomials $l(F)$ we mean the minimum length (number of summands) among all the $2^n$ canonical polarized polynomials of $F$. The Shannon function $L(n)$ for estimating the complexity of functions in $n$ variables in the class of canonical polarized polynomials is defined as $L(n)=\max l(F)$, where the maximum is taken over all functions $F$ in $n$ variables. Here we present the results of investigations of the function $L(n)$.

UDC: 519.713

Received: 16.12.1991


 English version:
Discrete Mathematics and Applications, 1994, 4:3, 273–277

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024