RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Forthcoming papers 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

 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.
Author to whom correspondence should be addressed

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:

UDC: 519.714

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{https://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{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85064338634}