This article is cited in 1 paper

Asymptotics for the Complexity of Boolean Functions with Small Number of Ones

N. P. Red'kin

Lomonosov Moscow State University

Abstract: The class $F_{n,k}$ of Boolean functions consisting of all functions of $n$ variables each of which outputs $1$ at exactly $k$ $n$-tuples of values of the variables is considered. For small $k$, for example, for $k<\ln n$, an asymptotics for the complexity of implementation of every function in $F_{n,k}$ by a circuit of functional elements in an irredundant basis containing $x\to y$ and $\overline{x\to y}$ is found.

Keywords: Boolean function, circuit, complexity of a function.

UDC: 519.95

Received: 05.02.2020

DOI: 10.4213/mzm12691

 English version: Mathematical Notes, 2021, 109:2, 256–261

Bibliographic databases:

• 
• 
•