2015/01/14 by Sergey Granin, Granin, Sergey, Yura Maximov +1
Computer Science · Mathematics · #Combinatorics (math.CO) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #cs.CC #math.CO
paper · pdf · doi:10.48550/arxiv.1501.03444
8 pages, in Russian
arxiv created 2015/01/14 · arxiv updated 2015/01/15
In this paper we establish some bounds on the complexity of disjunctive normal forms of boolean function from narrow subclasses (e.g. functions takes value 0 in a limited number of points). The bounds are obtained by reduction the initial problem to a simple set covering problem. The nature of the complexity bounds provided is tightly connected with Shannon effect and semi-effect for this classes.