RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Impact factor Subscription Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Diskr. Mat.: Year: Volume: Issue: Page: Find

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

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)$.

Full text: PDF file (534 kB)

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

Bibliographic databases:
UDC: 519.713

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

Citation in format AMSBIB
\Bibitem{Sup93} \by V.~P.~Suprun \paper Complexity of Boolean functions in the class of canonical polarized polynomials \jour Diskr. Mat. \yr 1993 \vol 5 \issue 2 \pages 111--115 \mathnet{http://mi.mathnet.ru/dm682} \mathscinet{http://www.ams.org/mathscinet-getitem?mr=1250961} \zmath{https://zbmath.org/?q=an:0829.94013} \transl \jour Discrete Math. Appl. \yr 1994 \vol 4 \issue 3 \pages 273--277 

• http://mi.mathnet.ru/eng/dm682
• http://mi.mathnet.ru/eng/dm/v5/i2/p111

 SHARE:

Citing articles on Google Scholar: Russian citations, English citations
Related articles on Google Scholar: Russian articles, English articles

This publication is cited in the following articles:
1. 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
2. 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
3. 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
4. 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: This page: 545 Full text: 223 First page: 1