Expressing Linear Orders Requires Exponential-Size DNNFs

• Abstract
• Abstract (translated by Google)
• URL
• PDF

Abstract

We show that any DNNF circuit that expresses the set of linear orders over a set of $n$ candidates must be of size $2^{\Omega(n)}$. Moreover, we show that there exist DNNF circuits of size $2^{O(n)}$ expressing linear orders over $n$ candidates.

Abstract (translated by Google)

URL

http://arxiv.org/abs/1807.06397

PDF

http://arxiv.org/pdf/1807.06397