  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:      Citing articles on Google Scholar: Russian citations, English citations
Related articles on Google Scholar: Russian articles, English articles
•  Number of views: This page: 64 References: 4 First page: 5 Contact us: math-net2019_05 [at] mi-ras ru Terms of Use Registration Logotypes © Steklov Mathematical Institute RAS, 2019