KIAM Main page Web Library  •  Publication Searh  Русский 
Publication

Article collection "Mathematical Problems of Cybernetics" №22, Moscow, 2024
Authors: Kochergin V.V., Mihajlovich A.V.
On the non-monotone complexity of Boolean and k-value logic functions
Abstract:
The paper discusses major advances in various extensions of inversion complexity problem accomplished in the past ten years. In the 1950s, A.A. Markov solved the problem of inversion complexity for Boolean functions. He determined the exact number of inverters in logic circuits of a special type for an arbitrary Boolean function. Precisely, these circuits contained inverters with unit weight and monotone functions with zero weights. In the paper we present, among other findings: the exact value of non-monotone complexity for any Boolean function; the exact value of inversion complexity for k-valued logic functions over a basis containing only monotone functions along with either Post or Lucasiewicz negations; upper and lower bounds of the non-monotone complexity for every k-valued logical function. The difference between these upper and lower bounds is constant and independent of the basis used. We also touch upon the problem of Boolean function circuit complexity over infinite bases. First, we present a sufficiently thorough overview of this problem. Second, we determine the exact value of complexity for an arbitrary Boolean function over a basis that consists of negation and all monotone functions.
Keywords:
Boolean circuits, logic circuits, circuit complexity, inversion complexity, nonmonotone complexity, bases with zero weight elements, infinite bases, multi-valued logic functions
Publication language: russian,  pages: 101 (p. 51-151)
Research direction:
Mathematical problems and theory of numerical methods
Russian source text:
Export link to publication in format:   RIS    BibTeX
About authors:
  • Kochergin Vadim Vasilievich,  orcid.org/0000-0002-7798-9502Lomonosov Moscow State University
  • Mihajlovich Anna Vitalievna,  orcid.org/0000-0002-3549-0260National Research University Higher School of Economics