A Class of Logic Functions Expressible by Polynomial-Size Binary Decision Diagrams
Nagisa Ishiura, Shuzo Yajima · Kyoto University Research Information Repository (Kyoto University) · 1991
In this paper we discuss properties of logic functions expressible by BDD's of feasible size.We define a class of logic functions expressible by BDD's whose size (number of nodes) are bounded by a polynomial of the number of input variables.We derive some properties of this class through the discussion on the relation between polynomial- size BDD's and Turing machines.We also focus on the relation between polynomial- size BDD's and combinational circuits and show that polynomial size BDD's can be synthesized into $O(\log^{2}n)$ depth combinational circuits.