DNF complexity of complete boolean functions
arXiv:1501.01331
Abstract
In this paper we analyse the complexity of boolean functions takes value 0 on a sufficiently small number of points. For many functions this leads to the analysis of a single function attains 0 only on unsigned representation of numbers from 1 to d for various d. Here we obtain a tight bounds on the DNF complexity of complete functions in terms of the number of literals and conjunctions. The method is based on a certain efficient approximation of the hypercube covering problem related to DNF complexity of a given boolean function.
19 pages, 1 figure, in Russian