Abstract Structuredd-DNNFs and SDDs are restricted negation normal form circuits used in knowledge compilation as target languages into which propositional theories are compiled. Structuredness is imposed by so-called vtrees. By definition SDDs are restricted structuredd-DNNFs. Beame and Liew (2015) as well as Bova and Szeider (2017) mentioned the question whether structuredd-DNNFs are really more general than SDDs w.r.t. polynomial-size representations (w.r.t. the number of Boolean variables the represented functions are defined on.) The main result in the paper is the proof that a function can be represented by SDDs of polynomial size if the function and its complement have polynomial-size structuredd-DNNFs that respect the same vtree.

Branching problems are considered as a nonuniform model of computation in complexity theory as well as a data structure for boolean functions in several applications. In many applications (e.g., verification), exact representations are required. For learning boolean functions f on the basis of classified examples, it is sufficient to produce the representation of a function g approximating f. This motivates the investigation of the size of the smallest branching program approximating f. Although several non-approximability results are contained in the papers on randomized branching programs, these results often do not work for the uniform distribution (which is the most important one in applications). Here, the following non-approximability results are presented. (1) It is proven that a simple function from the branching program literature requires exponential size to be approximated with respect to the uniform distribution by OBDDs, which are the most important type of branching programs in applications. (2) The first truly exponential lower bound on the size of approximating syntactic read-k-times branching programs with respect to the uniform distribution and error probability 1/2-2/sup -/spl Omega/(n)/, n the input size, is shown. In order to improve upon the so far best results for error probabilities smaller than 1/3, a strong combinatorial lemma from a recent paper of Ajtai on linear-length branching programs is exploited.

Branching programs (BPs) are a well-established computation and representation model for Boolean functions. Especially read-once branching programs (BP1s) have been studied intensively. Exponential lower bounds on the BP1 complexity of explicit functions have been known for a long time. Nevertheless, the proof of exponential lower bounds on the read-once branching program size of selected functions is sometimes difficult. Motivated by the applications the BP1 complexity of fundamental functions is of interest. It took quite a long time until Ponzio [16, 17] was able to prove a bound of 2^{Ω(\sqrt{n})} for integer multiplication. Combining results and methods for universal hashing with lower bound techniques for BP1s a lower bound of Ω(2^{n/4}) on the size of BP1s for integer multiplication is presented in this paper.

Ordered binary decision diagrams are a useful representation of Boolean functions, if a good variable ordering is known. Variable orderings are computed by heuristic algorithms and then improved with local search and simulated annealing algorithms. This approach is based on the conjecture that the following problem is NP-complete. Given an OBDD G representing f and a size bound s, does there exist an OBDD G* (respecting an arbitrary variable ordering) representing f with at most s nodes? This conjecture is proved.