Expressing Linear Orders Requires Exponential-Size DNNFs

This report considers a technical question that plays a role in the investigation of the expressivity and efficiency of different knowledge representation formalisms for social choice applications. In particular, we consider the formalism of Boolean circuits in Decomposable Negation Normal Form (DNNF) (or DNNF circuits). This is a formalism that has been studied in the setting of knowledge compilation and that enjoys many positive algorithmic properties [2]. We study the question whether the formalism of DNNF circuits can be used to express linear preferences in an efficient and compact way.