Implementation complexity of Boolean functions with a small number of ones

N. P. Red'kin

Lomonosov Moscow State University

Abstract: We consider the class $F_{n,k}$ consisting of $n$-ary Boolean functions that take the value one on exactly $k$ input tuples. For small values of $k$ the class $F_{n,k}$ is splitted into subclasses, and for every subclass we find the asymptotics of the Shannon function of circuit implementation in the basis $\{x\&y,\overline x\}$ (or in the basis $\{x\vee y,\overline x\}$); the weights of the basic gates are arbitrary strictly positive numbers.} \classification[Funding]{Research was supported by Russian Foundation for Basic Research (project No. 8.01.00337 “Problems of synthesis, complexity and reliability in theory of control systems”).

Keywords: Boolean function, Boolean circuit, Shannon function.

UDC: 519.714.4

Received: 03.10.2019

DOI: 10.4213/dm1592

 English version: Discrete Mathematics and Applications, 2021, 31:4, 271–279

Bibliographic databases:

• 
• 
• 
•