2015/01/06 by Yura Maximov, Maximov, Yura
Computer Science · Mathematics · #Coding theory and cryptography #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Formal Methods in Verification #cs.CC #math.CO
paper · pdf · doi:10.48550/arxiv.1501.01331
19 pages, 1 figure, in Russian
arxiv created 2015/01/06 · openalex publication_date 2015/01/06 · arxiv updated 2015/01/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.