Sentential decision diagrams (SDDs) introduced by Darwiche in 2011 are a
promising representation type used in knowledge compilation. The relative
succinctness of representation types is an important subject in this area. The
aim of the paper is to identify which kind of Boolean functions can be
represented by SDDs of small size with respect to the number of variables the
functions are defined on. For this reason the sets of Boolean functions
representable by different representation types in polynomial size are
investigated and SDDs are compared with representation types from the classical
knowledge compilation map of Darwiche and Marquis. Ordered binary decision
diagrams (OBDDs) which are a popular data structure for Boolean functions are
one of these representation types. SDDs are more general than OBDDs by
definition but only recently, a Boolean function was presented with polynomial
SDD size but exponential OBDD size. This result is strengthened in several
ways. The main result is a quasipolynomial simulation of SDDs by equivalent
unambiguous nondeterministic OBDDs, a nondeterministic variant where there
exists exactly one accepting computation for each satisfying input. As a side
effect an open problem about the relative succinctness between SDDs and free
binary decision diagrams (FBDDs) which are more general than OBDDs is answered.

本文旨在确定哪些布尔函数可以由小型的 SDDs 表示，同时将多项式大小的布尔函数表示集合与来自 Darwiche 和 Marquis 经典知识编译地图的表示类型进行比较。最主要的结果是通过等效的不明确的非确定性 OBDDs 对 SDDs 进行准多项式仿真，回答了 SDDs 和超过 OBDDs 的 FBDDs 相对简洁性之间的一个开放问题。