Affiliations: Faculty of Computational Mathematics and Cybernetics, Lomonosov Moscow State University, MGU, Vorobjovy Gory, Moscow, 119899, Russia. [email protected]; [email protected]
Note: [] Address for correspondence: Faculty of Computational Mathematics and Cybernetics, Lomonosov Moscow State University, MGU, Vorobjovy Gory, Moscow, 119899, Russia
Abstract: In this paper we study the representation of Boolean functions by general binary decision diagrams (BDDs). We investigate the size L(Σ) (number of inner nodes) of BDD Σ with different constraints on the number M(Σ) of its merged nodes. Furthermore, we introduce a weighted complexity measure W(Σ) = L(Σ) + ωM(Σ), where ω > 0. For the hardest Boolean function on n input variables we define the weight WBDD(n) and the size LBDD(n,t), where t limits the number of merged nodes. By using a new synthesis method and appropriate restrictions for the number t of merged nodes, we are able to prove tight upper and lower asymptotic bounds: WBDD(n) = 2n/n (1 + log n ± O(1)/n), LBDD(n,t) = 2n/log nt (1 ± O(1/n)), which have a relative error of O(1/n). Our results show how weight and structural restrictions of general BDDs influence the complexity of the hardest function in terms of high accuracy asymptotic bounds.
