On the complexity of analysis and manipulation of Boolean functions in terms of decision graphs (Q1330665)

One of the fundamental problems in computer-aided circuit design is the task of representing logic functions. Although, in principle, any valid representation is allowed, some representations may be preferred because they are more efficient in memory, more efficient to manipulate, or more indicative of the complexity of the final implementation. The search of an optimal trade-off between these competing objectives -- succinct representation of Boolean functions and feasible manipulation algorithms -- is a central theme of computer-aided logic synthesis. One candidate which seems to satisfy these two conditions is the concept of decision graphs or branching programs. The paper reports results of a systematic inspection of the computational complexity of basic tasks of Boolean manipulation such as satisfiability, tautology test, equivalence test, and binary Boolean synthesis in terms of different restricted types of branching programs.