On the complexity of Boolean functions with small number of ones
Николай Петрович Редькин · Discrete Mathematics and Applications · 2004
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 ⊕ y and x ⊕ y ⊕ 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.