|
This article is cited in 5 scientific papers (total 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)$.
Received: 16.12.1991
Citation:
V. P. Suprun, “Complexity of Boolean functions in the class of canonical polarized polynomials”, Diskr. Mat., 5:2 (1993), 111–115; Discrete Math. Appl., 4:3 (1994), 273–277
Linking options:
https://www.mathnet.ru/eng/dm682 https://www.mathnet.ru/eng/dm/v5/i2/p111
|
Statistics & downloads: |
Abstract page: | 689 | Full-text PDF : | 311 | First page: | 1 |
|