High Accuracy Asymptotic Bounds on the BDD Size and Weight of the Hardest Functions

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 W_BDD(n) and the size L_BDD(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: W_BDD(n) = 2ⁿ/n (1 + log n ± O(1)/n), L_BDD(n,t) = 2ⁿ/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.