This article is cited in 4 scientific papers (total in 4 papers)
Complexity of Boolean functions in the class of canonical polarized polynomials
V. P. Suprun
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)$.
PDF file (534 kB)
Discrete Mathematics and Applications, 1994, 4:3, 273–277
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
Citation in format AMSBIB
\paper Complexity of Boolean functions in the class of canonical polarized polynomials
\jour Diskr. Mat.
\jour Discrete Math. Appl.
Citing articles on Google Scholar:
Related articles on Google Scholar:
This publication is cited in the following articles:
S. N. Selezneva, “On the complexity of the representation of functions of many-valued logics by polarized polynomials”, Discrete Math. Appl., 12:3 (2002), 229–234
M. A. Bashov, S. N. Selezneva, “On the length of functions of $k$-valued logic in the class of polynomial normal forms modulo $k$”, Discrete Math. Appl., 25:3 (2015), 131–136
Svetlana N. Selezneva, “Complexity of systems of functions of Boolean algebra and systems of functions of three-valued logic in classes of polarized polynomial forms”, Discrete Math. Appl., 26:2 (2016), 115–124
S. N. Selezneva, “Upper bound for the length of functions over a finite field in the class of pseudopolynomials”, Comput. Math. Math. Phys., 57:5 (2017), 898–903
|Number of views:|