RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PERSONAL OFFICE
General information
Latest issue
Archive
Impact factor
Subscription
Guidelines for authors
License agreement
Submit a manuscript

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



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






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


Mat. Zametki, 2019, Volume 105, Issue 1, Pages 32–41 (Mi mz11693)  

Exact Value of the Nonmonotone Complexity of Boolean Functions

V. V. Kochergina, A. V. Mikhailovichb

a Lomonosov Moscow State University
b National Research University Higher School of Economics, Moscow

Abstract: We study the complexity of the realization of Boolean functions by circuits in infinite complete bases containing all monotone functions with zero weight (cost of use) and finitely many nonmonotone functions with unit weight. The complexity of the realization of Boolean functions in the case where the only nonmonotone element of the basis is negation was completely described by A. A. Markov: the minimum number of negations sufficient for the realization of an arbitrary Boolean function $f$ (the inversion complexity of the function $f$) is equal to $\lceil\log_{2}(d(f)+1)\rceil$, where $d(f)$ is the maximum (over all increasing chains of sets of values of the variables) number of changes of the function value from 1 to 0. In the present paper, this result is generalized to the case of the computation of Boolean functions over an arbitrary basis $B$ of prescribed form. It is shown that the minimum number of nonmonotone functions sufficient for computing an arbitrary Boolean function $f$ is equal to $\lceil\log_{2}(d(f)/D(B)+1)\rceil$, where $D(B)=\max d(\omega)$; the maximum is taken over all nonmonotone functions $\omega$ of the basis $B$.

Keywords: Boolean (logical) circuits, circuits of functional elements, circuit complexity, inversion complexity, nonmonotone complexity.

DOI: https://doi.org/10.4213/mzm11693

Full text: PDF file (476 kB)
First page: PDF file
References: PDF file   HTML file

English version:
Mathematical Notes, 2019, 105:1, 28–35

Bibliographic databases:

Document Type: Article
UDC: 519.714
Received: 24.05.2017

Citation: V. V. Kochergin, A. V. Mikhailovich, “Exact Value of the Nonmonotone Complexity of Boolean Functions”, Mat. Zametki, 105:1 (2019), 32–41; Math. Notes, 105:1 (2019), 28–35

Citation in format AMSBIB
\Bibitem{KocMik19}
\by V.~V.~Kochergin, A.~V.~Mikhailovich
\paper Exact Value of the Nonmonotone Complexity of Boolean Functions
\jour Mat. Zametki
\yr 2019
\vol 105
\issue 1
\pages 32--41
\mathnet{http://mi.mathnet.ru/mz11693}
\crossref{https://doi.org/10.4213/mzm11693}
\elib{http://elibrary.ru/item.asp?id=36603823}
\transl
\jour Math. Notes
\yr 2019
\vol 105
\issue 1
\pages 28--35
\crossref{https://doi.org/10.1134/S0001434619010048}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000464727500004}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85064338634}


Linking options:
  • http://mi.mathnet.ru/eng/mz11693
  • https://doi.org/10.4213/mzm11693
  • http://mi.mathnet.ru/eng/mz/v105/i1/p32

    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
  • Математические заметки Mathematical Notes
    Number of views:
    This page:64
    References:4
    First page:5

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