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






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


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

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


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
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

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


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

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    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  mathnet  crossref  mathscinet  zmath
    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  mathnet  crossref  crossref  mathscinet  isi  elib  elib
    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  mathnet  crossref  crossref  mathscinet  isi  elib
    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  mathnet  crossref  crossref  mathscinet  isi  elib
  • Дискретная математика
    Number of views:
    This page:545
    Full text:223
    First page:1

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020