Expressing Linear Orders Requires Exponential-Size DNNFs
arXiv:1807.06397v3
Originality Incremental advance
AI Analysis
This addresses a fundamental problem in computational complexity and knowledge representation, providing tight exponential lower bounds for DNNF circuits in expressing linear orders, which is incremental but precise.
The paper proves that any DNNF circuit expressing linear orders over n candidates must have size at least exponential in n, specifically 2^{Ω(n)}, and also constructs DNNF circuits of size 2^{O(n)} to show this bound is tight.
We show that any DNNF circuit that expresses the set of linear orders over a set of $n$ candidates must be of size $2^{Ω(n)}$. Moreover, we show that there exist DNNF circuits of size $2^{O(n)}$ expressing linear orders over $n$ candidates.