On the complexity of Boolean functions with a small number of ones

N. P. Red'kin

Diskretnaya Matematika, Tome 16 (2004) no. 4, pp. 20-31

Résumé

We consider the class of Boolean functions $F_{n,k}$ consisting of all functions in $n$ variables such that each of them takes value one exactly for $k$ tuples of variables. We obtain linear in $n$ estimates of the complexity of realisation of functions in $F_{n,k}$ by circuits of functional elements over the basis containing all Boolean functions in two variables except the linear functions $x \oplus y$ and $x\oplus y\oplus 1$. It follows from these estimates that for small $k$, for example, for $k\ln n$, the well-known Finikov method provides asymptotically minimal circuits for all functions of $F_{n,k}$. In some cases, the known lower bounds for complexity of circuits give a possibility to prove the minimality of the corresponding circuits. The research was supported by the Russian Foundation for Basic Research, grant 02–01–00985, by the program of President of Russian Federation for support of leading scientific schools, grant 1807.2003.1, and by the program ‘Universities of Russia.’